IT 279: Algorithms and Data Structures, Week 6 Heap
Priority Queues
could be implemented as a list, but that has efficiency issues.
At least one of insertion and deletion will be O(n).
Binary heaps are an alternative that offers better performance
Min Binary Heap: Min binary tree + a complete tree(insert from the left child)
percolate up: when inserting a smaller value in a min binary heap
Constant to insert the value at the end.
Must swap with a parent at most height of the tree -1 times.
Height: O(log n) b/c complete tree
delete minimum
1. replace the root value with the last value in the heap (reduce the size of the heap)
2. Fix the Heap: Percolate Down (if the smallest child is smaller than the parent, swap)
Minimum priority value is in the root:
Constant time to access that node
Heap Drawback
Often want to maintain FIFO ordering of items with the same priority
Heaps do not do that
heapify(max heap):
1. check the last parent node and compare it with their children
2. swap with the largest child if there is a larger one.
3. check again the children until they don't have any children.
Progress Check 14 on Heaps
In Big-Oh terms, what is the maximum height of a complete tree with n nodes?
O(log n)
True or false: Heaps are normally implemented in arrays.
True
Which of the following is used when inserting into a binary heap?
Which of the following is used when deleting the minimum value from a minimum binary heap?
Progress Check 15 on More Heaps
Insertion into a binary heap takes: O(log n)
The buildHeap(or heapify) process uses: percolateDown
What is the runtime of the buildHeap(or heapify) process? O(n)