Read heaps first.
A binary heap uses a complete binary tree.
Recall that complete binary trees:
- have each level filled, with possible exception of last level
- when the last level is incomplete all nodes are filled from the left
Inserting into a binary heap:
- place new element in left most spot (n+1)
- "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
Extracting the dominator from a binary heap:
- remove dominating element from top
- move last added element (bottom-right most leaf) into top
- "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.
2 7 8 1 5 9 3 pushed into min-heap as a tree:
1 2 3 7 5 9 8
But as an array looks like:
Notice this is equivalent to a breadth-first traversal.
This image from Wikipedia explains best:
So for some zero-based index
- left child =
2i + 1
- right child =
2i + 2
- parent =
floor((i-1) / 2)
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.
floor(n/2) is the index of one or more the the middle items of the array:
floor(n/2)if n is odd
floor(n/2) - 1if n is even
- append number to list
parent = heap[floor((i-1)/2)]
- if parent < number then swap them
Test your inserts
- Test your removals
- cannot be efficiently searched because it is not a BST
- we don't know any facts that will improve a linear search
- get the dominating element, e.g.
We can store any binary tree in an array without pointers but:
- array still requires empty spots for missing nodes
- methods to save memory make it less flexible
8.4. heapq — Heap queue algorithm.