Final Review 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; 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; the root will always contain the (lowest/highest) priority value element Methods peek(): returns (but does not remove) the item with the highest priority; runtime is Θ(1) removeMin(): returns (and does remove) the item with the highest priority; 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 first open bottom-left position ∗ Bubble up the new inserted value Bubbling (in 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 (pick the lesser of the children if both have priority value less than n) 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 a min heap, methods include T poll(), T peek(), void push(T item) Can use own Comparat

Lire le document entier