5.1 Priority queue interface

A time sharing operating system manages many processes ready to run and assigns priorities to them influenced by various criteria (nice, history of run time of the process, etc.). The opsys runs a process for a chunk of time, interrupts it, adjusts it's priority, inserts it in the ready queue, extracts the highest priority ready process and launches it. This action repeats each at each process timeout and at other interrupts such as printer becoming ready to accept a job.

The functions needed by the priority queue data structure for the above scenario are these.

• P.init(): initialize P to be a empty queue.
• P.insert(x): put x in the priority queue.
• x = P.extract_highest(): extract the highest priority element.

  Sometimes this function is also needed:

• P.heighten_key(xp, k): for the item in P referenced by xp, decrease the key to k.

  Note: For historical reasons the number measuring the priority is often interpreted such that the smallest number represents the highest priority. Thus extract_highest() is often called extract_min(), and heighten_key() called decrease_key().

Let us consider a couple of ways to represent a priority queue.

1. Maintain P as an unsorted sequence. Inserting is constant time: just add an element. Likewise decrease_key is constant time: just adjust an element. extract_highest, however, costs Θ(n) time, for n = size(P).

2. Maintain P as a sorted sequence. Extract_highest is constant time: just remove the first element. However inserting costs Θ(n) time, for n = size(P), as we saw in insertion_sort. Likewise decrease_key is problematic.

Thus we seek priority queue representations in which all three of these key operations are fast (we want log(n) or better).