COMPSCI 61B Lecture Notes - Lecture 20: Comparator, Binary Tree, Priority Queue
Document Summary
Can only interact with the smallest item - care more about quickly finding the smallest or largest element instead of quickly searching. Useful if you want to keep track of the smallest, largest, best, etc. Adt that optimizes for handling minimum or maximum elements. Monitor the text messages of the citizens to make sure that they are not having any unharmonious conversations. Each day, you prepare a report of the m messages that seem most unharmonious using the harmoniousnesscomparator. Create a list of all messages sent for the entire day and sort it using your comparator. Potentially uses a huge amount of memory (n) where n is number of texts. Goal: do this in (m) memory using a minpq. Can track m transactions using only m memory. Api for minpq also makes code very simple. 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.
