Priority Queues

other uses for heaps

A Priority Queue maintains a set of S elements, each element associated with a key. Priority Queues are used for queuing systems and event simulation.

Methods:

Heap-Insert ( S, x )  :: S ¬ S È { x }

Maximum ( S ) :: returns max

Heap-Extract-Max ( S ) ::  returns and removes max

Running Times:

Heap-Extract-Max : O ( lg n )

Heap-Insert : O ( lg n )

Heap-Extract-Max (A)

1. if heap-size[A] < 1

2.        then error "heap underlfow"

3. max ¬ A[1]

4. A[1] ¬ A[heap-size[A]}

5. heap-size[A] ¬ heap-size[A] - 1

6. Heapify ( A, 1 )

7. return max

Heap-Insert ( A, key )

1. heap-size[A] ¬ heap-size[A] + 1

2. i ¬ heap-size[A]

3. while i > 1 and A[Parent (i)] < key

4.        do A[i] ¬ A[Parent (i)]

5.               i ¬ Parent (i)

6. A[i] ¬ key

The operation of Heap-Insert