Priority Queues and Heaps

The motivation for priority queues can be illustrated through the following scenario (Top-K problem):

• Imagine we are monitoring text messages between citizens to identify unharmonious conversations.

• Each day, we generate a report of the top $M$ messages that are the most unharmonious.

This is a general case of finding the largest or smallest element, known as the Top-1 problem. To solve this type of problem, we can use priority queues, which can be implemented with various underlying data structures, including ordered arrays, bushy BSTs, and hash tables.

public interface MinPQ<Item> {
    public void add(Item x);
    public Item getSmallest();
    public Item removeSmallest();
    public int size();
}

Implementing PQs: Heaps

We can use heap (bushy BSTs) to implement a priority queue. For example, using a min-heap, each node of which is less than or equal to both of its children, we can implement a min priority queue, where the item with the least priority is at the head of the queue.

Heap Operations

• add: Add to the end of heap temporarily. Swim up the hierarchy to the proper place. Swimming involves swapping nodes if child < parent

• getSmallest: Return the root of the heap (This is guaranteed to be the minimum by our min-heap property

• removeSmallest: Swap the last item in the heap into the root. Sink down the hierarchy to the proper place. Sinking involves swapping nodes if parent > child. Swap with the smallest child to preserve min-heap property.

Implementation

Approach 1: Intuitively, store explicit references in the nodes to make a tree.

Approach 2: through arrays.

public class Tree2<Key> {
  Key[] keys;
  int[] parents;
  ...
}

Screenshot 2024-07-08 at 20.12.00

Yet the parents array in this approach is redundant and we can simply discard it.

public class TreeC<Key> {
  Key[] keys;
  ...
}

And the swim operation can be implemented as:

public void swim(int k) {
    if (keys[parent(k)] ≻ keys[k]) {
       swap(k, parent(k));
       swim(parent(k));              
    }
}

We will use this implementation for heaps and thereby for priority queues. We will leave one empty spot at the beginning of the array to simplify computation.

• leftChild(k) = $k \times 2$

• rightChild(k) = $k \times 2 + 1$

• parent(k)= $k / 2$

Other Implementations

Screenshot 2024-07-08 at 20.37.11