Week 11: Heaps, Greedy Algorithms & Tries

1. Priority Queues & the Top-K Pattern

std::priority_queue is a binary heap wrapped in a container adaptor — push and pop run in O(log n), and top() always returns the largest element in O(1) (a max-heap by default). Give it greater<T> as a comparator and it becomes a min-heap instead.

priority_queue_basics.cpp

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

int main() {
    // Max-heap (default): largest element on top
    priority_queue<int> maxHeap;
    maxHeap.push(5); maxHeap.push(1); maxHeap.push(9);
    int largest = maxHeap.top();   // 9, O(1)
    maxHeap.pop();                 // O(log n)

    // Min-heap: pass container type + greater<T> comparator
    priority_queue<int, vector<int>, greater<int>> minHeap;
    minHeap.push(5); minHeap.push(1); minHeap.push(9);
    int smallest = minHeap.top();  // 1
}

The top-K pattern uses a min-heap capped at size k to find the k largest elements without sorting the whole input. Every time the heap grows past size k, evict the smallest element — whatever survives at the end is exactly the k largest values seen so far:

top_k.cpp

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

// Return the k largest elements, unordered -- O(n log k) time, O(k) space
vector<int> kLargest(const vector<int>& nums, int k) {
    priority_queue<int, vector<int>, greater<int>> minHeap;
    for (int x : nums) {
        minHeap.push(x);
        if ((int)minHeap.size() > k) minHeap.pop();   // evict the current smallest
    }
    vector<int> result;
    while (!minHeap.empty()) {
        result.push_back(minHeap.top());
        minHeap.pop();
    }
    return result;
}

Min-heap for the K LARGEST is not a typo

It feels backwards the first time: a min-heap of size k, not a max-heap, finds the k largest elements. The min-heap only ever needs to know its smallest member so it can decide what to evict — this keeps the heap capped at size k, giving O(n log k) instead of the O(n log n) a full sort would cost.

2. Greedy Algorithms & Interval Scheduling

A greedy algorithm builds a solution by making the locally best choice at each step and never reconsidering it. Greedy doesn't work for every problem — it's correct only when the problem has the greedy-choice property (a locally optimal choice leads to a globally optimal solution) and optimal substructure (an optimal solution contains optimal solutions to subproblems).

The classic proving ground is interval scheduling: given a set of intervals, select the maximum number that don't overlap. The greedy rule is to always sort by end time and pick the interval that finishes soonest among those still available:

interval_scheduling.cpp

#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

// Maximum number of non-overlapping intervals -- O(n log n)
int maxNonOverlapping(vector<pair<int,int>> intervals) {
    sort(intervals.begin(), intervals.end(),
         [](const pair<int,int>& a, const pair<int,int>& b) {
             return a.second < b.second;   // sort by END time
         });

    int count = 0;
    int lastEnd = INT_MIN;
    for (auto& [start, end] : intervals) {
        if (start >= lastEnd) {   // doesn't overlap the last chosen interval
            count++;
            lastEnd = end;
        }
    }
    return count;
}

The proof sketch is an exchange argument: suppose an optimal solution's first pick isn't the interval with the earliest end time. Swapping it out for the earliest-ending interval can only free up more room for everything that comes after — it never makes the remaining choices worse, and it might make them better. Repeating this exchange shows the greedy choice is always at least as good as any alternative.

Sort by end time, not start time

Sorting by start time and greedily picking is a classic wrong-answer trap — a long interval that starts early can block out several short ones that would together beat it. Sorting by end time guarantees each greedy pick leaves the maximum possible room for future picks.

3. Huffman Coding: Greedy with a Heap

Huffman coding builds an optimal prefix-free binary code for a set of characters based on their frequencies — frequent characters get shorter codes. It's a direct application of the "repeatedly combine the two cheapest things" greedy pattern, implemented with a min-heap:

huffman.cpp

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

struct HuffmanNode {
    char ch;
    int freq;
    HuffmanNode* left;
    HuffmanNode* right;
    HuffmanNode(char c, int f, HuffmanNode* l = nullptr, HuffmanNode* r = nullptr)
        : ch(c), freq(f), left(l), right(r) {}
};

struct Compare {
    bool operator()(HuffmanNode* a, HuffmanNode* b) const {
        return a->freq > b->freq;   // min-heap: smallest frequency on top
    }
};

// Build a Huffman tree from (character, frequency) pairs -- O(n log n)
HuffmanNode* buildHuffmanTree(const vector<pair<char,int>>& freqs) {
    priority_queue<HuffmanNode*, vector<HuffmanNode*>, Compare> pq;
    for (auto& [c, f] : freqs) pq.push(new HuffmanNode(c, f));

    while (pq.size() > 1) {
        HuffmanNode* a = pq.top(); pq.pop();
        HuffmanNode* b = pq.top(); pq.pop();
        pq.push(new HuffmanNode('\0', a->freq + b->freq, a, b));
    }
    return pq.top();   // root of the Huffman tree
}

At every step the two least-frequent nodes are merged into a new internal node whose frequency is their sum, and that new node goes back into the heap. Merging the two smallest first guarantees the least-frequent characters end up deepest in the tree (longest codes) and the most-frequent characters stay shallow (shortest codes) — exactly what minimizes the total encoded length.

A reusable pattern, not just a compression algorithm

"Repeatedly combine the two cheapest things via a min-heap" shows up under different names across interview problems — minimum cost to connect ropes, last stone weight, and reorganizing strings all reduce to the same heap-driven greedy loop as Huffman coding.

4. Tries for Prefix Search & Autocomplete

A trie (prefix tree) stores strings character by character along paths from the root, so every node represents a shared prefix. Unlike a hash set of full strings, a trie can answer "does any word start with this prefix?" without scanning the whole dictionary:

trie.cpp

#include <string>
#include <unordered_map>
using namespace std;

struct TrieNode {
    unordered_map<char, TrieNode*> children;
    bool isEndOfWord = false;
};

class Trie {
public:
    Trie() { root = new TrieNode(); }

    // O(L) where L = word length
    void insert(const string& word) {
        TrieNode* node = root;
        for (char c : word) {
            if (node->children.find(c) == node->children.end())
                node->children[c] = new TrieNode();
            node = node->children[c];
        }
        node->isEndOfWord = true;
    }

    // O(L)
    bool search(const string& word) const {
        TrieNode* node = find(word);
        return node != nullptr && node->isEndOfWord;
    }

    // O(L) -- true if ANY inserted word starts with prefix
    bool startsWith(const string& prefix) const {
        return find(prefix) != nullptr;
    }

private:
    TrieNode* root;

    TrieNode* find(const string& s) const {
        TrieNode* node = root;
        for (char c : s) {
            auto it = node->children.find(c);
            if (it == node->children.end()) return nullptr;
            node = it->second;
        }
        return node;
    }
};

Autocomplete builds directly on startsWith: walk down to the node representing the typed prefix, then DFS from that node collecting every path that hits isEndOfWord == true, reconstructing each full word as you go.

O(L), not O(N)

A trie's insert/search cost depends only on the length of the word being processed, never on how many other words are already stored — a hash set of N strings still costs O(L) per lookup on average, but can't answer "which words share this prefix?" without scanning everything.

5. Hands-on Exercise

Hands-on

Build a K-Way Autocomplete Engine

Combine this week's heap and trie skills into a single feature, then apply the greedy interval pattern to a scheduling check.

Requirements:

Implement a Trie class with insert and a collectWithPrefix(prefix) method that returns all stored words starting with prefix, using DFS from the prefix's node.
Implement topKFrequent(vector<string>& words, int k) using a min-heap ordered by frequency (with alphabetical order as a tie-break), returning the k most frequent words in descending frequency order.
Combine the two: implement autocomplete(prefix, k) that uses your trie to find all matching words and your heap to return only the top k by frequency.
Implement canAttendAllMeetings(vector<pair<int,int>>& intervals) using this week's interval-scheduling technique, returning true only if no two meetings overlap.
Test edge cases: an empty prefix (should return the global top-K), a prefix with zero matches, and frequency ties.

Hint

For the tie-break, write a comparator struct that returns true when "a should be evicted before b" — for a min-heap over (frequency, word) that means lower frequency first, and among equal frequencies, put the alphabetically LATER word first so it's evicted first, leaving the earlier word in the results.

6. Knowledge Check

Four quick questions. Expand each to check your answer.

Why is a min-heap used to find the K largest elements, instead of a max-heap?

The heap only needs to answer one question — "what's the smallest element currently in my top-K set?" — so it knows what to evict when a bigger candidate arrives. A max-heap would put the largest element on top, which is the opposite of what you need to decide evictions, and it would have to grow to hold all n elements instead of staying capped at size k.

Why does sorting intervals by end time, not start time, make the greedy interval-scheduling algorithm correct?

Picking the interval that finishes earliest leaves the maximum possible room on the timeline for every interval chosen afterward, which is provable by an exchange argument. Sorting by start time instead can lock in a long interval that blocks out several shorter, non-overlapping intervals that would together have produced a better answer.

Why does Huffman coding always merge the two lowest-frequency nodes at each step, and how does that relate to greedy exchange arguments?

Merging the two least-frequent nodes first forces them to end up deepest in the resulting tree, which is where the longest codes live — and since they're the rarest characters, that's exactly where you want the cost concentrated. As with interval scheduling, an exchange argument shows that swapping any other pair in first can never produce a shorter total encoding than merging the two smallest.

Why is a trie's search/insert complexity O(L) rather than O(N), where N is the number of words already stored — and when would a trie beat a hash set?

Every trie operation walks exactly one character at a time down a path whose length equals the word being processed — it never touches the other stored words, so N doesn't factor into the cost at all. A trie beats a hash set specifically when you need prefix queries: "which words start with this prefix" is a single subtree walk in a trie, but requires scanning every entry in a hash set of full strings.