Stephen's Sidebar

2.5: A More Complex Data Structure: Priority Queues

One of the book's key focuses is to seek algorithms that improve qualitatively on brute-force search, and the priority queue can help a lot with this.

A priority queue is a first in first out collection that allows ordering by priority. This can be useful in real-time events such as the scheduling of processes on a computer. Each process has a priority, but process do not arrive in order of their priorities.

A Data Structure for Implementing a Priority Queue

Heaps are used in the implementation of Priority Queues - balanced binary trees in which each child is at at least as large as its parent's. When adding/removing items from this heap we need to order them as well in a logn time - this calls for algorithms that iterate in the worst case through the heap's height. When needing to travel up the heap:

Heapify-up(H, i):

if i > 1 then
  let j = parent(i) = [i/2]
  if key[H[i]]<key[H[j]] then
    swap the array entries H[i] and H[j]
    Heapify-up(H, j)

this swaps the child/parent when the child is smaller than the parent, thus moving it up the tree @ O(logn) runtime.

When needing to travel down the heap:

Heapify-down(H, i):

Let n = length(H)
If 2i> n then
  terminate with H unchanged
else if 2i< n then
  Let left = 2i and right 2i+1  
  Let j be the index that minimizes key[H[left]] and key[H[right]]
else if 2i == n then
  Let j = 2i
if key[H[j]] < key[H[i]] then
  swap the array entries H[i] and H[j]
  Heapify-down(H, j)

this swaps the child/parent when the parent is bigger than the child.

Here is a list of the runtimes of heap operations:

StartHeap(N) returns an empty heap H that is set up to store at most N elements. O(n).
Insert(H, v) inserts the item v into heap H. If the heap currently has n elements, O(logn).
FindMin(H) identifies minimum element. O(1).
Delete(H, i) deletes the element in heap position i. O(logn).
ExtractMin(H) identifies and deletes an element with the minimum key value from a heap. This combines delete and FindMin - O(logn).

This section was interesting and helped me learn the runtimes of the heap much better. 10/10.