Table of Contents
1. Intro to Priority Queues
Figure 1: A drawing of a linear structure. Elements have positions like usual: 0, 1, 2, 3, and 4. However, each element also has a priority number, with the largest number at the front and smallest number at the back. The elements also have data, which is the item to be "processed".
A Priority Queue is a type of queue where each item in the queue has a priority. High priority items are "processed" before low priority items.
A normal Queue has Push, Front, Pop, and IsEmpty functionality. A Priority Queue's version of Push requires a priority level, and its access and removal functionality works on the highest priority item.
Since items are stored based on priority, a higher priority item might be inserted, requiring items in the queue to be reorganized - or re-sorted based on their priorities.
Review 1. Let's say we have the following outgoing emails-to-be-sent as elements of our priority queue:
| front | back | |
|---|---|---|
| PRIORITY: 3 | PRIORITY: 2 | PRIORITY: 1 |
| Subject: "Your account is overdrawn!" | Subject: "Make sure to get a flu shot!" | Subject: "Sale on hoodies!" |
Which email gets sent first?
2. Simple Priority Queue
We can implement a basic priority queue by creating a "PQNode" to store each element's data and priority #…
template <typename T> struct PQNode { T data; int priority; };
Then within a BasicPriorityQueue class, store a vector of PQNodes.
template <typename T> class BasicPriorityQueue { public: BasicPriorityQueue(); void Push( int priority, T data ); void Pop(); T& Peek(); void Display() const; private: vector< PQNode<T> > m_array; void ShiftRight( size_t index ); void ShiftLeft( size_t index ); };
Review 2. Here we use a function called "Peek" instead of "Front" to access the top-priority item. We're going to design the priority queue so that the top priority item is at index 0. Therefore, Peek and Pop operate on which element of the array?
Review 3. If we're going to keep higher-priority items to the left of the array (towards index 0) and lower-priority things to the right of the array (towards the array size), when we push a new item with some priority…
PQNode newNode;newNode.priority = VALUE; // any integer newNode.data = "Cat";
… Where will it go?
2.1. Example priority queue
Let's look at this basic priority queue:
| index | 0 | 1 | 2 | 3 | 4 |
| priority/value | 100/ lunch | 75/ homework | 50/ cats | 25/ sleep |
Review 4. What will be returned when Peek() is called?
Review 5. If we're inserting a new item, snacks (priority = 80), what index will it be inserted at? _
Review 6. If we're inserting a new item, mow lawn (priority = 5), what index will it be inserted at? _
Review 7. If we retrieve the top-priority item then remove it from the PriorityQueue, what will happen to the rest of the items in the queue?
3. Heap Priority Queue
We can also build a priority queue off of a Heap (which can also be built on top of an array or list).
template <typename T> class HeapPriorityQueue { public: void Push( int priority, T data ); void Pop(); T& Peek(); void Display() const; private: void Heapify( size_t index ); vector< PQNode<T> > m_array; };
Recall that a heap is treated like a binary tree, but its elements are stored in a linear format.
Figure 2: A binary tree heap. Breakfast, priority 100, is the root. Breakfast's left child is Lunch at 75. Breakfast's right child is Dinner at 50. Lunch's right child is Snacks at 25.
| index | 0 | 1 | 2 | 3 |
| priority/value | 100/ breakfast | 75/ lunch | 50/ dinner | 25/ snacks |
Review 8. A max-heap is invalid if…
Review 9. Heap Nodes fill in from…
Review 10. HeapPeek: If a heap is not empty, then its top-priority item will be at the root Node, which is at index _ .
3.1. Heap Push
Remember that for a node at index i:
- Its parent, if it exists, is
items[(i - 1) / 2]
The Heap's Push function can be implemented as:
void HeapPriorityQueue<T>::Push( int priority, T data ) { PQNode<T> newNode; newNode.data = data; newNode.priority = priority; m_array.push_back( newNode ); size_t i = m_array.size() - 1; while ( i != 0 && m_array[ (i-1)/2 ].priority < m_array[i].priority ) { swap( m_array[i], m_array[ (i-1) / 2 ] ); i = (i - 1) / 2; } }
Review 11. To begin with, the new node is inserted where in the array? (before the while loop)
Review 12. The condition
m_array[ (i-1)/2 ].priority < m_array[i].priority
is comparing…
Review 13. If the condition is true, then what two items are swapped
Review 14. If the condition is true, what does i become after the swap?
3.2. Heap Pop
Heap's Pop can be implemented like:
void HeapPriorityQueue<T>::Pop() { if ( m_array.size() == 0 ) { throw Exception::StructureEmptyException( "Heap::Pop", "Can't pop from empty structure!" ); } if ( m_array.size() == 1 ) { m_array.pop_back(); return; } m_array[0] = m_array.back(); m_array.pop_back(); Heapify( 0 ); }
Review 15. When the array has more than 1 item and we wish to remove the top-priority one, what happens here with this code?
Review 16. Given this heap:
Figure 3: A binary tree heap. Breakfast, priority 100, is the root. Breakfast's left child is Lunch at 75. Breakfast's right child is Dinner at 50. Lunch's right child is Snacks at 25.
Which of these diagrams represent the heap just before the Heapify function is called?
3.3. Heapify
Remember that for a node at index i:
- Its left child, if it exists, is
items[2 * i + 1] - Its right child, if it exists, is
items[2 * i + 2]
The Heapify function works like this:
void HeapPriorityQueue<T>::Heapify( size_t index ) { size_t left = 2 * index + 1; size_t right = 2 * index + 2; // Is this subtree out of order? size_t largest = index; if ( left < m_array.size() && m_array[left].priority > m_array[largest].priority ) { largest = left; } if ( right < m_array.size() && m_array[right].priority > m_array[largest].priority ) { largest = right; } if ( largest != index ) { swap( m_array[largest], m_array[index] ); Heapify( largest ); } }
Review 17. What is the first if statement doing in this function?
Review 18. What is the second if statement doing in this function?
Review 19. What is the third if statement doing?
Review 20. In the third if statement where doe the recursive function call go?