AlgoVerse

Priority queue with a heap

Insert into a max-heap by sifting the new item up, and extract the maximum by sifting the item placed at the root down; both O(log n).

A priority queue always hands out the largest item first. With a max-heap (a complete tree where no node is smaller than its children, stored in an array) both operations take O(log n):

Read the full explanation ↓
Input:
n=10 · target=15PDF export

A ten-item heap; key 15 rises to one level below the root, then the maximum (16) is extracted.

  1. def priority_queue(heap, key):
  2. insert(heap, key)
  3. top = extract_max(heap)
  4. return top, heap
  7. def insert(heap, key):
  8. heap.append(key)
  9. i = len(heap) - 1
  10. while i > 0:
  11. parent = (i - 1) // 2
  12. if heap[parent] >= heap[i]:
  13. break
  14. heap[i], heap[parent] = heap[parent], heap[i]
  15. i = parent
  18. def extract_max(heap):
  19. top = heap[0]
  20. heap[0] = heap[-1]
  21. heap.pop()
  22. i = 0
  23. size = len(heap)
  24. while True:
  25. largest = i
  26. left = 2 * i + 1
  27. right = 2 * i + 2
  28. if left < size:
  29. if heap[left] > heap[largest]:
  30. largest = left
  31. if right < size:
  32. if heap[right] > heap[largest]:
  33. largest = right
  34. if largest == i:
  35. return top
  36. heap[i], heap[largest] = heap[largest], heap[i]
  37. i = largest

Invariant: Apart from the one place being repaired, no node is larger than its parent.

Start

1614108793241target 1516014110283749536274819

Local variables

key15

Orange = changed in this step

heap list

1614108793241

Call stack

  1. priority_queue()line 1
Step 1 of 61
Black = inserted, extracted · Orange = key stepcompare: 0/8 · swap: 0/4 · append: 0/1 · inserted: 0/1 · move_last: 0/1 · extracted: 0/1

    How the work grows with input size

    Average of 12 random graphs per n (fixed seeds). Hollow marker = the input on screen.

    • comparisons
    • swaps
    • current input (n=10)
    02468468101214n = number of itemscomparisonsswaps
    Show as a table
    ncomparisonsswaps
    43.80.9
    65.21.8
    86.12.2
    107.22.8
    127.63.3
    147.33.3
    Explanation

    The idea

    A priority queue always hands out the largest item first. With a max-heap (a complete tree where no node is smaller than its children, stored in an array) both operations take O(log n):

    • Insert: put the key at the end of the heap and, while it is larger than its parent, swap it with the parent (sift up).
    • Extract the maximum: take the root, put the last item at the root, and swap it with its larger child until it is not smaller than either child (sift down).

    Cost

    The heap is ⌊log n⌋ high and each operation walks at most one root-to-leaf path: O(log n). This is the queue that Dijkstra, Prim and job schedulers use.

    What to watch in the trace

    • The tree above the bars is the same array drawn as a heap.
    • Follow the new key on its way up, and the replacement root on its way down.