Source
Adapted from my own handwritten and hand-typed notes from Year 1 to Year 3 of my EEE degree
Array Indexing Recap
A maxheap is stored in A[1..n] (index 0 unused). For node :
The structure property (complete tree, last level filled from the left) and the order property (each node its children) must both hold after every operation. The two repair tools are siftdown (move a small value down) and siftup (move a large value up).
Recursive Siftdown
This is the code version of the siftdown idea: swap with the larger child until the node has no child or is already larger than its children.
def swap(A, i, j):
A[i], A[j] = A[j], A[i]
def siftdown(A, i):
n = len(A) - 1 # heap is A[1..n]
largest = i
left = 2 * i
if left <= n and A[left] > A[i]:
largest = left
right = 2 * i + 1
if right <= n and A[right] > A[largest]:
largest = right
if largest != i:
swap(A, i, largest)
siftdown(A, largest) # continue one level lowerSiftdown moves down at most the height of the tree, so it is .
Delete the Root
The root holds the maximum. Move the last element into the root, shrink the heap, then siftdown from the root.
def heap_delete_root(A):
n = len(A) - 1
A[1] = A[n] # last element replaces the root
A.pop(n) # remove the last cell
siftdown(A, 1)Delete Any Node
To delete node , move the last element A[n] into position and remove the last cell. The moved value may be too small or too large for its new place:
if A[i // 2] >= A[i]: # parent still larger
siftdown(A, i)
else:
siftup(A, i)Example: deleting at index 2 moves the last value there. Its parent is larger, so is sifted down.

Insert a Value
A new value goes into the bottom level, farthest left free spot, i.e. index (if the bottom level is full, a new level starts at the left). Then siftup: swap with the parent while it is larger than the parent.
def heap_insert(A, val):
A.append(val) # position n + 1
i = len(A) - 1
while i > 1 and A[i // 2] < A[i]:
swap(A, i, i // 2) # move up one level
i = i // 2Example: inserting at index 13 under : swap with , then with , then stop under .

Complexity
| Operation | Time |
|---|---|
| siftdown, siftup | |
| heapify (build a maxheap) | |
| delete root, delete node, insert |
Heaps give a "weakly sorted" array cheaply, which is why they are used for heapsort and priority queues.