The active prefix of the array must represent a complete -ary tree, filled in the prescribed order, and must obey heap order:Equivalently, every parent is no larger than each existing child. Repeatedly following parents shows that the root contains a global minimum. The array representation already provides the complete-tree shape; it is not enough to check only that the root is a minimum, since the inequality must hold throughout the d-ary min-heap. Assume integral throughout the heap operations.
Save the root, move the last active entry to the root, shrink the active prefix, then restore heap order by heapify down:Only edges descending from the moved entry can violate heap order. If the entry is no larger than every child, the entire heap is valid. Otherwise swapping with a minimum child restores the order at the old position: that child is no larger than the old entry or any sibling. Its original subtree was already ordered, so only the moved entry's new outgoing edges can remain invalid. This is the loop invariant of
ExtractMin(A):
if A.heap_size == 0:
error "empty heap"
answer = A[0]
A[0] = A[A.heap_size-1]
A.heap_size = A.heap_size-1
if A.heap_size > 0:
SiftDown(A,0)
return answer
SiftDown(A,i):
while true:
best = i
for j = 0,...,d-1:
c = Child(i,j)
if c >= A.heap_size:
break
if A[c] < A[best]:
best = c
if best == i:
return
swap A[i], A[best]
i = bestSiftDown. Each swap moves it down one level, proving termination and correctness.For , the height is , and selecting a minimum child costs at most comparisons per level. Thus
ExtractMin takes time, with auxiliary storage. Empty and singleton heaps take constant time. For , there is at most one nonroot level and the loop examines at most actual children, taking ; this also lies within for . The coarser uniform expression safely includes all small sizes.A decreased key can violate heap order only against its parent. An inserted entry begins at the next free position and uses the same repair:Here is a sentinel at least as large as every permitted key. One can equivalently write
DecreaseKey(A,i,key):
if i < 0 or i >= A.heap_size:
error "invalid index"
if key > A[i]:
error "key increased"
A[i] = key
while i > 0:
p = Parent(i)
if A[p] <= A[i]:
return
swap A[p], A[i]
i = p
Insert(A,key):
ensure capacity for A.heap_size+1 entries
i = A.heap_size
A.heap_size = A.heap_size+1
A[i] = +infinity
DecreaseKey(A,i,key)key directly into the new entry and run the upward loop, avoiding any sentinel representation.At every upward swap, the smaller key moves above its larger parent; the displaced parent remains no larger than the entries below it, as follows from the old heap order. Thus only the new parent edge can be invalid. At most one parent comparison is needed per level, with no scan of siblings. Both operations take time in the usual range, or uniformly including tiny heaps and large .
The heap-operation bound assumes space for the inserted entry. A capacity expansion in a dynamic array can cost for that individual insertion; sufficient preallocation avoids it, while geometric capacity growth adds only constant amortized allocation cost per insertion.
Dijkstra's algorithm solves the single-source shortest path problem in a finite weighted graph with nonnegative edge weights. Given a source , it computes for every vertex the minimum sum of edge weights on a path from to , reporting if is unreachable. Keeping a shortest-path predecessor also recovers the corresponding paths. Directed graphs are allowed; an undirected graph can be represented by two oppositely directed edges. Negative edge weights are outside the algorithm's standard correctness assumptions, while zero weights are allowed.
Use an indexed priority queue of unsettled vertices, keyed by their tentative distances. Initialize the source to zero and other keys to . Each
ExtractMin settles the currently closest vertex. Scan its outgoing edges; whenever edge relaxation improves a neighbour's tentative distance, update that neighbour with DecreaseKey. Already settled vertices need no further update, by the correctness of Dijkstra's algorithm for nonnegative weights.There are at most extractions and at most successful decreases. The indexed priority queue maintains each vertex's current array position and updates this index table on every swap, so locating a key for
DecreaseKey costs . Preallocate capacity . Repeated insertion costs , or bottom-up heap construction initializes the queue in time. Scanning adjacency lists costs in total.For and , the heap-operation contributions are thereforeand the overall bound isA uniform bound including larger arity and tiny graphs is . Arity greater than the number of vertices offers no useful extra heap levels. These bounds assume adjacency lists; with an adjacency matrix, scanning neighbours contributes instead. No rebuilding of the heap is required after each decrease.
Articles by others on the same topic
There are currently no matching articles.