Page 212 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 10: Heaps

In the worst case, the hole must be pushed from the root to a leaf node. Each iteration of the loop Notes
makes at most two object comparisons and moves the hole down one level.
Therefore, the running time of the dequeueMin operation is
⎣log n⎦(τ〈isLT〉 + τ〈isLE〉) + O(log n),
2
where n = count is the number of items in the heap. If τ〈isLT〉 = O(1) and τ〈isLE〉 = O(1), the
dequeueMin operation is simply O(log n) in the worst case.

Task Discuss the uses of binary heaps.

10.3 Applications of Heaps

The main applications of heaps are:
1. Discrete Event Simulation

2. Implementation

10.3.1 Discrete Event Simulation

One of the most important applications of priority queues is in discrete event simulation. Simulation
is a tool which is used to study the behavior of complex systems. The first step in simulation is

modeling. You construct a mathematical model of the system I wish to study. Then you write a
computer program to evaluate the model.

The systems studied using discrete event simulation have the following characteristics: The system
has a state which evolves or changes with time. Changes in state occur at distinct points in
simulation time. A state change moves the system from one state to another instantaneously.
State changes are called events.

Example: Suppose I wish to study the service received by customers in a bank. Suppose
a single teller is serving customers. If the teller is not busy when a customer arrives at the bank,
the that customer is immediately served. On the other hand, if the teller is busy when another
customer arrives, that customer joins a queue and waits to be served.
You can model this system as a discrete event process as shown in Figure 10.5. The state of the
system is characterized by the state of the server (the teller), which is either busy or idle, and by
the number of customers in the queue. The events which cause state changes are the arrival of a
customer and the departure of a customer.

Figure 10.5: A Simple Queueing System
customers

arriving customer departing customer

queue server

If the server is idle when a customer arrives, the server immediately begins to serve the customer
and therefore changes its state to busy. If the server is busy when a customer arrives, that customer
joins the queue.

LOVELY PROFESSIONAL UNIVERSITY 207