Table of Contents

1. Intro to Priority Queues

example-pq.png

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?

  • ○ Your account is overdrawn
  • ○ Sale on hoodies
  • ○ Make sure to get a flu shot
  • ○ They all have equal chance of getting processed 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?

  • ○ The item at index m_array.size()-1
  • ○ The item at index 0
  • ○ The item at m_array[ PRIORITY ]

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?

  • ○ We will store newNode at m_array[0]
  • ○ We will store newNode at m_array[m_itemCount]
  • ○ We will store newNode at m_array[m_array.size()-1]
  • ○ We will store newNode at some location where \[m_array[x].priority >= newNode.priority >= m_array[y].priority\]

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?

  • ○ cats
  • ○ homework
  • ○ lunch
  • ○ sleep

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?

  • ○ Everything moves forward (left) by 1. Now homework is the top priority.
  • ○ Everything moves backward (right) by 1. Now sleep is the top priority.
  • ○ Everything moves forward (right) by 1. Now cats is the top priority.
  • ○ Everything moves backwards (left) by 1. Now lunch is the top priority.

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.

tree-pq.png

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…

  • ○ Any Node has a child larger than itself.
  • ○ Any Node has a child equal to itself.
  • ○ Any Node has a child less than itself.

Review 9. Heap Nodes fill in from…

  • ○ Left-to-right
  • ○ Right-to-left

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)

  • ○ At the beginning of the array
  • ○ In the middle of the array
  • ○ At the end of the array

Review 12. The condition

m_array[ (i-1)/2 ].priority < m_array[i].priority

is comparing…

  • ○ Whether the index at position i is larger than the parent at index \(\frac{1-i}{2}\).
  • ○ Whether the index \(\frac{1-i}{2}\) is larger than the parent at index i.
  • ○ Whether the current node at position i's priority is larger than its parent at position \(\frac{1-i}{2}\)'s priority.
  • ○ Whether the current node at position \(\frac{1-i}{2}\)'s priority is larger than its parent at position i's priority.

Review 13. If the condition is true, then what two items are swapped

  • ○ A node and its parent
  • ○ A node and its left child
  • ○ A node and its right child
  • ○ A node and the root node of the tree.

Review 14. If the condition is true, what does i become after the swap?

  • ○ The index of the left child node.
  • ○ The index of the right child node.
  • ○ The index of the parent node.
  • ○ The index of the root node.

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?

  • ○ The root node moves to the end of the array, to the bottom of the tree.
  • ○ The root node is overwritten with the last node in the array.
  • ○ The node swaps places with its largest child node.

Review 16. Given this heap:

tree-pq.png

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?

  • Option A:

    pq-question1-a.png

    Figure 4: A binary tree with the root as 25 / Snacks. Snacks left child is 75 / Lunch. Snacks right child is 50 / Dinner.

  • Option B:

    pq-question1-b.png

    Figure 5: A binary tree with the root as 25 / Snacks. Snack's left child is 75 / Lunch. Snack's right child is 50 / Dinner. Lunch's left child is 100 / Breakfast.

  • Option C:

    pq-question1-c.png

    Figure 6: A binary tree with 75 / Lunch as the root. Lunch's left child is 50 / Dinner. Lunch's right child is 100 / Breakfast. Dinner's left child is 25 / Snacks.

  • Option D:

    pq-question1-d.png

    Figure 7: A binary tree with 100 / Snacks as the root. Snack's left child is 75 / Lunch. Snack's right child is 50 / Dinner. Lunch's left child is 25 / Breakfast.

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?

  • ○ Checking to see if there is a left child, and if the left child's priority is greater than the current node's priority.
  • ○ Checking to see if there is a right child, and if the right child's priority is greater than the current node's priority.
  • ○ Checking to see if there is a left parent, and if the left parent's priority is greater than the left child's priority.
  • ○ Checking to see if there is a right parent, and if the right parent's priority is greater than the right child's priority.

Review 18. What is the second if statement doing in this function?

  • ○ Checking to see if there is a left child, and if the left child's priority is greater than the current node's priority.
  • ○ Checking to see if there is a right child, and if the right child's priority is greater than the current node's priority.
  • ○ Checking to see if there is a left parent, and if the left parent's priority is greater than the left child's priority.
  • ○ Checking to see if there is a right parent, and if the right parent's priority is greater than the right child's priority.

Review 19. What is the third if statement doing?

  • ○ If the largest index is not the current node's index, then swap the current node with the larger child node.
  • ○ If the largest index is not the current node's index, then swap the current node with the larger parent node.
  • ○ If the largest index is not the current node's index, then swap the current node with the smaller child node.

Review 20. In the third if statement where doe the recursive function call go?

  • ○ To the location of the largest child node (before it got swapped with the current node).
  • ○ To the location of the largest smallest node (before it got swapped with the current node).
  • ○ To the location of the largest parent node (before it got swapped with the current node).
  • ○ To the location of the smallest parent node (before it got swapped with the current node).

Author: RachelWil

Created: 2026-10-14 Wed 11:12

Validate