Capstone: Build a Discrete-Event Simulator

August 2026 · 20 min read

The series ends with something to build rather than read. A discrete-event simulator is the purest application of a priority queue — it is a heap with a loop around it — and it exercises nearly everything from the previous sixteen parts. After that, a curated problem list and a self-assessment.

The Capstone: A Discrete-Event Simulator

Simulate a bank with k tellers. Customers arrive at known times, each needing a known service duration, and are served first-come-first-served by whichever teller frees up soonest. Report each customer's wait and the overall average.

The core insight, and the reason this is the right capstone: the simulation clock does not tick. It jumps from event to event. The event queue is a min-heap keyed by time, and simulated time is simply the time of whatever event you just popped. Nothing between two events can affect the outcome, so nothing between them needs simulating.

#include <queue>
#include <vector>
#include <cstdio>

struct Event {
    long long time;
    int       type;         // 0 = arrival, 1 = departure
    int       customer;

    // min-heap by time; arrivals before departures at equal time
    bool operator>(const Event& o) const {
        if (time != o.time) return time > o.time;
        return type > o.type;
    }
};

struct Customer { long long arrival, duration, start; };

int main() {
    std::vector<Customer> customers = {
        {0, 5, -1}, {1, 3, -1}, {2, 7, -1}, {3, 2, -1}, {10, 4, -1}
    };
    const int k = 2;

    std::priority_queue<Event, std::vector<Event>, std::greater<Event>> events;
    for (int i = 0; i < (int)customers.size(); ++i)
        events.push({customers[i].arrival, 0, i});

    std::priority_queue<long long, std::vector<long long>, std::greater<long long>> freeAt;
    for (int i = 0; i < k; ++i) freeAt.push(0);      // all tellers free at t = 0

    std::queue<int> waiting;
    long long totalWait = 0;

    while (!events.empty()) {
        Event e = events.top();
        events.pop();
        long long now = e.time;                      // the clock IS the event time

        if (e.type == 0) waiting.push(e.customer);

        while (!waiting.empty() && !freeAt.empty() && freeAt.top() <= now) {
            int c = waiting.front();
            waiting.pop();
            freeAt.pop();

            customers[c].start = now;
            totalWait += now - customers[c].arrival;
            long long done = now + customers[c].duration;
            freeAt.push(done);
            events.push({done, 1, c});               // schedule the departure
        }
    }

    std::printf("average wait: %.2f\n", (double)totalWait / customers.size());
}

Two heaps, each doing a distinct job: one orders events in time, the other tracks which teller frees soonest. That is Part 10's template and Part 9's two-container arrangement in the same program.

Extensions, in rough order of difficulty

1. Priority customers. Replace the FIFO waiting queue with a max-heap keyed on priority. Add a sequence number to break ties, or service order becomes non-deterministic — Part 15, item 7.
2. Reneging. Customers leave if they wait longer than T. Now you must remove a queued customer — use lazy deletion from Part 12.
3. Statistics. Report the median and p95 wait using the two-heap technique from Part 9, without storing all samples sorted.
4. Scale. Push to ten million events and profile. Try a 4-ary heap from Part 13 and measure whether it helps.
5. Verify. Write a brute-force simulator that ticks one time unit at a time and assert both produce identical output on random inputs. This is the differential-testing habit from Part 3, and it is how you actually establish correctness.

Curated Problem Catalog

Ordered so that each tier builds on the one before.

Tier 1 — Mechanics

• Last Stone Weight easy — repeated extraction, nothing else.
• Kth Largest Element in a Stream easy — the bounded heap in its simplest form.
• Relative Ranks easy — heap versus sort; notice sort is fine here.
• Take Gifts From the Richest Pile easy — pop, transform, push.

Tier 2 — The Core Patterns

• Kth Largest Element in an Array medium — compare against nth_element.
• Top K Frequent Elements medium — also solve it with bucket sort in O(n).
• K Closest Points to Origin medium — watch the overflow.
• Sort Characters By Frequency medium
• Meeting Rooms II medium — write both the heap and sweep-line versions.
• Task Scheduler medium — then derive the O(n) closed form.
• Reorganize String medium — greedy on the most frequent remaining.
• Single-Threaded CPU medium — clock jumping.

Tier 3 — Composition

• Merge k Sorted Lists hard — heap and divide-and-conquer.
• Find Median from Data Stream hard — the two-heap archetype.
• Kth Smallest Element in a Sorted Matrix medium — also solvable by binary search on the answer.
• Find K Pairs with Smallest Sums medium
• Network Delay Time medium — Dijkstra.
• Path with Minimum Effort medium — Dijkstra with a max-edge key.
• Min Cost to Connect All Points medium — Prim.
• Maximum Number of Events That Can Be Attended medium

Tier 4 — Hard

• Sliding Window Median hard — two heaps plus lazy deletion.
• IPO / Maximum Capital hard — two heaps on different keys.
• Course Schedule III hard — regret greedy.
• Minimum Cost to Hire K Workers hard — sort by ratio, heap on quality.
• Smallest Range Covering Elements from K Lists hard
• Minimum Number of Refueling Stops hard — regret over fuel already passed.
• Trapping Rain Water II hard — a heap-driven flood fill in 2D; a genuinely different use.
• Swim in Rising Water hard — Dijkstra on a grid with a max key.

Self-Assessment

You have the material if you can do all of these without notes:

1. Write sift_up and sift_down from memory, with the correct unsigned guard and bounds check.
2. Explain why bottom-up build is O(n) and reproduce the summation.
3. Say instantly which heap direction a top-k problem needs, and justify it in one sentence.
4. Implement the two-heap median with correct rebalancing.
5. Write Dijkstra with lazy deletion and explain what the stale check does.
6. Give three cases where a heap is the wrong tool, with the right one for each.
7. Explain why std::priority_queue has no decrease-key, and two ways around it.
8. Spot a comparator that is not a strict weak ordering.

Closing Thought

The heap is worth studying carefully because it is the clearest example in elementary algorithms of a structure defined by what it refuses to promise. A BST orders everything; a heap orders only along root-to-leaf paths. That one deletion buys perfect balance for free, which buys the array encoding, which buys zero allocation and excellent cache behaviour on the hot path.

That is the transferable lesson: the strength of a data structure often comes from the guarantees it declines to make. When you next design one, the useful question is not only “what must this support?” but “what can I refuse to support, and what does refusing buy me?”

Start with the series overview if you want to revisit any part.