7-Priority Queues and Heaps

Summary

Priority queues return items by priority (not insertion order). Heaps are the common data structure used to implement priority queues efficiently, supporting fast lookup of the highest (or lowest) priority and dynamic insert/remove operations.

Priority Queues

  • Store items with an associated priority score.

  • Common operations:

    • insert(item, priority) — add an item.

    • peek() — return highest-priority item (null if empty).

    • remove() — remove & return highest-priority item (null if empty).

    • is_empty(), size().

  • Use cases: packet scheduling, spellcheck suggestions, best-first search, task triage (e.g., ER), ranked recommendations.

Implementations & Trade-offs

  • Sorted list/array: peek() O(1), insert() O(N) (must place new item in order).

  • Unsorted list/array: insert() O(1), peek() / remove() O(N) (must scan).

  • Heap: balances costs — peek() O(1), insert() O(log N), remove() O(log N). Good when both insertions and extractions are frequent.

Heaps (Max-Heap)

  • Heap property (max-heap): each node ≥ its children. Root = maximum.

  • Array representation (packed array, root at index 1):

    • Left child of node at i → 2*i

    • Right child → 2*i + 1

    • Parent of node at i → floor(i / 2)

  • Keep array_size and last_index (virtual end). Preallocate to avoid frequent resizes.

Heap Insert (Bubble Up)

HeapInsert(heap, value):
    if heap.last_index == heap.array_size - 1:
        increase heap size
    heap.last_index += 1
    heap.array[heap.last_index] = value
    current = heap.last_index
    parent = floor(current / 2)
    while parent >= 1 and heap.array[parent] < heap.array[current]:
        swap(heap.array[parent], heap.array[current])
        current = parent
        parent = floor(current / 2)

  • Worst-case swaps ≈ tree height → O(log N).

Remove Max (Bubble Down)

HeapRemoveMax(heap):
    if heap.last_index == 0:
        return null
    result = heap.array[1]
    heap.array[1] = heap.array[heap.last_index]
    heap.array[heap.last_index] = null
    heap.last_index -= 1
    i = 1
    while i <= heap.last_index:
        swap = i
        if 2*i <= heap.last_index and heap.array[swap] < heap.array[2*i]:
            swap = 2*i
        if 2*i+1 <= heap.last_index and heap.array[swap] < heap.array[2*i+1]:
            swap = 2*i+1
        if i != swap:
            swap(heap.array[i], heap.array[swap])
            i = swap
        else:
            break
    return result

  • Also O(log N) worst-case.

Storing Auxiliary Info / Comparators

  • Store records (e.g. TaskRecord { priority, data... }).

  • Use a comparator helper (e.g. IsLessThan(a, b)) instead of raw < so heap works for composite types.

Updating Priorities

  • UpdateValue(heap, index, new_value):

    • Replace value

    • If new > old → bubble up

    • Else → bubble down

  • Finding an element’s index is not efficient in a heap; use a secondary map (hash table) to track item → heap index if updates by key are needed.

Min-Heap

  • Same structure but property reversed: parent ≤ children.

  • Implementation is identical except comparisons use > instead of <.

  • (Or negate priorities as a quick trick.)

Heapsort

  • Two phases:

    1. Build heap from all items.

    2. Repeatedly remove_max to produce sorted output (decreasing for max-heap).

  • Simple approach (insert all then extract all) gives:

    • Build: O(N log N)

    • Extraction: O(N log N)

    • Overall: O(N log N)

Complexity Summary

  • peek() (root lookup): O(1)

  • insert(): O(log N) worst-case

  • remove() (max/min): O(log N) worst-case

  • Build by repeated inserts: O(N log N)

  • Heapsort: O(N log N)

  • Space: O(N) (packed array)

Why It Matters

Heaps trade off searchable structure for prioritized retrieval and dynamic insert/remove efficiency. They keep the tree nearly complete so path lengths are small (≈ log N), making both insertion and extraction fast. Use heaps when you need frequent prioritized access but not arbitrary-value search.

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    // By default, priority_queue is a max-heap
    priority_queue<int> pq;

    // Insert elements
    pq.push(10);
    pq.push(30);
    pq.push(20);

    cout << "Priority Queue contents (max-heap):\n";
    while (!pq.empty()) {
        cout << pq.top() << " ";  // top() gives highest priority
        pq.pop();  // remove top element
    }
    cout << endl;

    // Min-heap example (use greater<int>)
    priority_queue<int, vector<int>, greater<int>> min_pq;
    min_pq.push(10);
    min_pq.push(30);
    min_pq.push(20);

    cout << "Priority Queue contents (min-heap):\n";
    while (!min_pq.empty()) {
        cout << min_pq.top() << " ";  
        min_pq.pop();
    }
    cout << endl;

    return 0;
}

import heapq

# Python heapq is a min-heap by default
pq = []
heapq.heappush(pq, 10)
heapq.heappush(pq, 30)
heapq.heappush(pq, 20)

print("Priority Queue contents (min-heap):")
while pq:
    print(heapq.heappop(pq), end=" ")
print()

# Max-heap example (invert values by pushing negative)
max_pq = []
heapq.heappush(max_pq, -10)
heapq.heappush(max_pq, -30)
heapq.heappush(max_pq, -20)

print("Priority Queue contents (max-heap):")
while max_pq:
    print(-heapq.heappop(max_pq), end=" ")
print()