Final Review Solutions Heaps Motivation: What if we always want to find the minimum or maximum element? Keep high priority items at the top Min heap: high priority corresponds to low priority value Max heap: high priority corresponds to high priority value Notice the difference between priority and priority value! Represented as a binary tree with two more properties: Complete: No empty spaces other than on the right-hand side of the bottommost level. Consequence: height will be Θ(log N ) where N is the number of nodes (Min/Max)-Heap property: for a particular node n, the children of n must have (greater/lesser) priority value than n. Consequence: the root will always contain the (lowest/highest) priority value element Methods (of a min-heap) peek(): returns (but does not remove) the item with the minimum priority value; runtime is Θ(1) removeMin(): returns (and does remove) the item with the minimum priority value; runtime is O(log N ) ∗ Take the item in the bottom-rightmost position and replace the value at the root ∗ Bubble down the new root value insert(T item, int priorityVal): Insert the item with priority value of priorityVal into the heap; runtime is O(log N ) ∗ Insert the item in the bottom-rightmost position ∗ Bubble up the new inserted value Bubbling (of a min-heap) Bubble up: while the priority value of a particular node n is less than the priority value of its parent, swap the two Bubble down: while the priority value of a particular node n is greater than the priority value of its child/children, swap the two (always pick the lesser of the two children if both have priority value less than the current node) 1 Representation Number each element in the heap, starting from 1, left to right top to bottom, this will represent the index of the item in the array! For a particular node at index i : ∗ Parent is at index 2i ∗ Left child is at index 2i ∗ Right child is at index 2i + 1 PriorityQueue<T> Implemented with min