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 MM 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;
  ...
}

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×2k \times 2

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

  • parent(k)= k/2k / 2

Other Implementations

PreviousDisjoint SetsNextSort

Last updated