Priority Queue
Intro
Priority queue is an abstract data type, in which each element has a "priority" associate with it. PQ supports operations such as findMin() in O(1), insert(element) and deleteMin in O(logn).
Here is a funny example from ADM: Single people maintain a priority queue of potential dating candidates—mentally if not explicitly. One’s impression on meeting a new person maps directly to an attractiveness or desirability score. Desirability serves as the key field for inserting this new entry into the “little black book” priority queue data structure. Dating is the process of extracting the most desirable person from the data structure (Find- Maximum), spending an evening to evaluate them better, and then reinserting them into the priority queue with a possibly revised score.
Heap
We can implement priority queue in different ways (unordered array, ordered array, linked list). One most efficient way is using a data structure called heap. A heap is a complete binary tree - all levels are full except the last level where all elements are placed to the left (So the height of the tree is guaranteed to be logn which will help out the runtime of our desired operations). In a min heap, all the children are greater than their parents. In a max heap, all parents are greater than their children.
Heap Implementation
Since the binary tree is complete, we know the location of the tree node if we know the index.
siftUp
siftDown
operations
Application
Data stream
Questions
References
- UW-Madison CS367 Lecture 24 Heaps and Priority Queues
- The Algorithm Design Manual Ch3.5 Priority Queue
- Heap and Heapsort by stoimen
- Algorithms, Part I - Week 4 Priority Queues by Robert Sedgewick