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 lower

Siftdown 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 // 2

Example: inserting at index 13 under : swap with , then with , then stop under .

Complexity

OperationTime
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.