Binary Heaps

Read heaps first.




A binary heap uses a complete binary tree.

Recall that complete binary trees:

Inserting into a binary heap:

  1. place new element in left most spot (n+1)
  2. “Bubble Up”: if and while (new) element dominates parent
    • swap them

Swaps happen between levels, and a tree will have lg(n) levels. Since there are n items to be inserted, insertion will take O(nlogn).

Extracting the dominator from a binary heap:

  1. remove dominating element from top
  2. move last added element (bottom-right most leaf) into top
  3. “Bubble Down”: if and while that element does not dominate its children:
    • swap it with lesser of two children

Implementing Binary Heaps

Since a binary heap is a complete binary tree we can implement it using an array.

Example: 2 7 8 1 5 9 3 pushed into min-heap as a tree:

  2   3
 7 5 9 8

But as an array looks like: 1,2,3,7,5,9,8,. Notice this is equivalent to a breadth-first traversal.

This image from Wikipedia explains best: Implicit Binary Tree

So for some zero-based index i:

WARNING: Beware zero and one-based version of the above equations. Many references use one-based equations because the math/logic is cleaner, but programmers always use zero-based arrays.

Notice that floor(n/2) is the index of one or more the the middle items of the array:

To insert:

  1. append number to list
  2. “Bubble Up”:
    • parent = heap[floor((i-1)/2)]
    • if parent < number then swap them


Heap Interface:

We can store any binary tree in an array without pointers but:


8.4. heapq — Heap queue algorithm.