COMP1927 - Priority Queues

A priority queue is an abstract data type; it is characterised not by how it is stored or how operations are performed, but by how the data is accessed externally.

(i.e the difference between a heap and a priority queue is that a heap is a priority queue, but a priority queue is not necessarily a heap).

Characterising Feature; Priority

The idea behind it is that elements are given priority (often simply by size), and the highest priority element is the first element, and the other elements are ordered correspondingly.

Operations

The two operations on a priority queue are push and pop (insert and deleteMax).

Implemented

Priority Queues can be implemented with a number of different data structures:

Ordered Array

Insert

To insert into an ordered array requires finding the insertion point (with a linear or binary search) and then shuffling all the other elements up in order to create space.

void insert (PQ p, int item) {
 
   int insertPlace;
   // Find the first element >= to item
   for (insertPlace = 0; p->pq[insertPlace] < item; insertPlace++) {
   }
 
   int i;
   // Move every element up to insertPlace up one
   for (i = p->last; i >= insertPlace; i--) {
      p->pq[i+1] = p->pq[i];
   }
 
   // Insert item into the correct place
   p->pq[insertPlace] = item;
   p->last++;
 
}

Delete

To delete from an ordered array is quite simple; return the last element and decrease the numElements counter by 1.

int delete (PQ p) {
 
   int result = p->pq[p->last];
   p->pq[p->last] = 0;
   p->last--;
 
   return result;
 
}

Unordered Array

The opposite is true about the simplicity of operations in an unordered array; insertion is very simple and deletion more complex.

Insert

Inserting into an unordered array is dead simple; just add the item to the end.

void insert (PQ p, int item) {
 
   p->pq[p->last+1] = item;
   p->last++;
 
}

Delete

Deleting from an unordered array is more complex; find the biggest item and then swap the last one with it.

int delete (PQ p) {
 
   int biggest = 0;
   int i;
 
   // Find the biggest element
   for (i = 1; i <= p->last; i++) {
      if (p->pq[i] > p->pq[biggest]) {
         biggest = i;
      }
   }
 
   // Set the result as the biggest
   int result = p->pq[biggest];
   // Swap the biggest with the last element
   p->pq[biggest] = p->pq[p->last-1];
   // Decrease the number of elements by 1
   p->last--;
 
   return result;
 
}

Heap

Using a heap allows us to do both of the insert and delete operations quite quickly and simply by adding in a bubble function.

Insert

Inserting into a heap requires adding the element to the end of the array, and then bubbling it up to the correct place.

Delete

Deleting from a heap requires swapping the first and last element and then bubbling the new first element down to the correct place.

Comparisons Between the Above

Insert Delete
Ordered O(n) O(1)
Unordered O(1) O(n)
Heap O(lg(n)) O(lg(n))

Heapsort

Heapsort works by putting all the items into a heap and then swapping the biggest to being the last element of the heap, hence sorting it.