Key Points
- Priority queue
- Stores items with keys that can be compared using
<(most commonly numbers). - Regardless of order of insertion, gives easy access to “most-important” item.
- “Most important” can be largest or smallest key.
- Stores items with keys that can be compared using
- Binary heap
- A binary tree such that
- The tree is complete (every level is full except the bottom, which is filled from left to right);
- The key in any node is the largest/smallest in its subtree.
- Usually encoded as an array rather than as a tree.
- The array contains the items in level order.
- Complexities:
- GET-MIN: \( \Theta(1) \)
- POP-MIN: \( \mathrm{O}( \log{n} ) \)
- INSERT: \( \mathrm{O}( \log{n} ) \)
- HEAPIFY: \( \Theta(n) \)
- (Turn an array in arbitrary order into a heap)
- A binary tree such that
- HEAPSORT
- A sorting algorithm that uses heap operations!
- Essentially, MAX-HEAPIFY then POP-MAX every item.
- Sorts an array of arbitrary numbers in \( \mathrm{O}( n \log n ) \) time.
- A sorting algorithm that uses heap operations!
(When logged in, completion status appears here.)