COMPSCI 61B Lecture Notes - Lecture 24: Quadtree, Comparator, Binary Tree
1 Jun 2017
School
Department
Course
Professor
Document Summary
Useful if you want to keep track of the smallest , largest , best , etc. seen so far. Can track top m transactions using only m memory. Api for minpq also makes code very simple (don"t need to do explicit comparisons) Bsts would work, but need to be kept bushy and duplicates are awkward. Binary min-heap: binary tree that is complete and obeys min-heap property. Min-heap: every node is less than or equal to both of its children. Complete: missing items only at the bottom level (if any), all nodes are as far left as possible. Lend themselves very naturally to implementation of priority queues. Swim up the hierarchy to your rightful place Swap the last item in the heap into the root. Then, sink your way down the hierarchy, yielding to most quali ed folks. To interpret array: simply assume tree is complete. Same as 3, but leave spot 0 empty.
