Priority Queue - Naive Implementation

In chapter 1, we reviewed priority queue operations. In short, a queue that supports an ordinary insertion operation at its rear, and a deletion operation that deletes according to some priority ordering is called a priority queue.

As we’ll see in the next chapter, the highest priority can be thought of as the minimum or the maximum element. In this and subsequent chapter, we’ll consider the minimum element as the highest priority. This is how the early processors were designed. Priority interrupts were associated with small integers, and the highest priority was 0.

Since we are considering the highest priority element as the minimum element in some appropriate numeric ordering, this delete operation is called deleteMin. For example, priority numbers can be assigned to the items so that priority 0 is the highest priority; priority 1 is second highest; 2 , third highest, and so on 1 Therefore, a priority queue is a queue that supports a deleteMin operation and an insert operation. No other operations are required.

The question is, what is a good data structure for this purpose. The performance measure of interest is not the cost of a single operation, but of a sequence of \(n\) insertions and deleteMin operations, in some arbitrary, unspecified order. Remember that a queue is only a buffer, in other words, a temporary storage place to overcome short term variations in the rate of insertion and deletion. In the long run, the size of a queue must remain constant otherwise it implies that the two processes inserting and deleting are mismatched and that sooner or later the queue will get too large. Therefore the number of insertions must be equal to the number of deleteMins in the long run.

Naïve Implementations

The naïve approach, i.e., the first one to come to mind, is to use an ordinary queue as a priority queue. Insertion is an \(O(1)\) operation and deletion is O(n), where \(n\) is the current size of the queue.

Naive Insert O(1)

insert(node) {
  list.append(node)
}

Naive Pull O(N)

pull() {
  highest = list.get_first_element()

  // iterate through each node in the queue and record highest seen
  foreach node in list {
     if highest.priority < node.priority {
         highest = node
     }
  }

  list.remove(highest)
  return highest
}

Since the queue must be searched each time for the minimum element. An alternative is to use a balanced binary search tree instead of a queue. Insertions and deletions in a balanced binary search tree are both \(O(\log n)\), but the overhead is high anyway.

The first suggestion, using an ordinary queue, will require \(O\left(n^{2}\right)\) operations in the worst case. This is because it will require roughly \(n / 2\) insertions, which is O(n), since each insertion takes constant time, and \(n / 2\) deletions, but each deletion takes time proportional to the queue size at the time of the deletion. In the worst case, all insertions take place first and the deletions take \(n / 2+(n / 2-1)+(n / 2-2)+\ldots+2+1=O\left(n^{2}\right)\) steps. On average, the insertions and deletions will be intermingled and the average queue size for a deletion will be \(n / 4\). This still leads to \(O\left(n^{2}\right)\) steps on average.

The use of a binary tree requires a slightly more complicated analysis.

These solutions are not efficient. They do not use the information available at the time of the insertion. When an item is inserted, we know its value. Knowing its value is a piece of information that can be used to position it within the queue data structure so as to make future deleteMin operations more efficient.