Course contentsShow
← Computer Science
Lesson 612 of 2,87214. Heaps and Priority QueuesFree lesson

Event-Driven Simulation

Use a min-heap priority queue to process events in chronological order for discrete event simulation.

Event-Driven Simulation

You'll learn how a min-heap priority queue manages events in chronological order for discrete event simulation.

The Core Idea

Event-driven simulation models systems where things happen at specific points in time—like customers arriving at a bank, packets traveling through a network, or tasks completing on servers. Instead of checking every millisecond "did anything happen?", we use a min-heap priority queue to store future events sorted by their scheduled time. The simulation repeatedly pulls the earliest event, processes it, and possibly schedules new events.

How It Works

Imagine you're simulating a hospital emergency room:

  1. Store events by timestamp: Each event has a time (e.g., "patient arrives at 3:15 PM" or "doctor finishes at 3:22 PM")
  2. Use a min-heap: The event with the smallest (earliest) time is always at the top
  3. Process chronologically: Extract the minimum event, handle it (update system state), and potentially insert new future events
  4. Repeat until done: Continue until the queue is empty or simulation time ends

Why Min-Heap?

From our earlier lessons, we know:

  • Extract-min: O(log n) — efficiently get the next event
  • Insert: O(log n) — efficiently schedule new events
  • Peek: O(1) — check what happens next without removing it

This beats checking an unsorted list (O(n) to find next event) or maintaining a sorted array (O(n) to insert).

Example Scenario

Simulating a print queue: Start with "job1 arrives at t=5", "job2 arrives at t=8". Extract job1 first, process it, insert "job1 completes at t=12". The heap automatically keeps everything in time order as the simulation unfolds.

Key Takeaway: Event-driven simulation uses a min-heap priority queue to efficiently process events in chronological order, extracting the earliest event and dynamically scheduling new ones as the simulation progresses.