Chapter 2.5: Priority Queues

A priority queue is designed for applications in which elements have a priority value or key and each time we want to select an element from a set S, we want to take the one with the highest priority. Smaller keys represent higher priorities. Priority queues are good for managing real-time evens such as the scheduling of processes on a computer. Each process has a priority, but they do not arrive in order of their priorities. The running time of each operation of a priority queue is O(logn). Sorting a priority queue of n items takes O(nlogn) time. We use heaps to implement priority queues. It is possible to use a list (sorted or unsorted) but both of those data structures put sorting the queue in O(n^2) which is larger than O(nlogn). Conceptually, a heap is a balanced binary tree. The tree has a root, and each node can have up to 2 children, a left and a right child. The keys in the tree are said to be in heap order if they key of any element is at least as large as it key of its parent node. To represent a heap, we can either use pointers, with pointers pointing to the parent node and children, or we can use an array, where node i has a left child at 2i, a right child at 2i+1, and a parent at floor(i/2). Heaps have the smallest key at the root, so identifying the minimal element takes O(1) time. Adding and deleting elements is a bit more complicated.

Consider adding a new element v and assume the heap has n<N elements so far. Now it has n+1 elements. Add the new element to the final position, i = n+1, of the heap, so H[i] = v. Now check and see if heap order is preserved, using the heapify-up algorithm. Let j = parent(i) = floor(i/2) be the parent node of i. Call H[j] = w. If key[v] < key[w] the swap the positions of v and w. And let j be the new i. Then call the function recursively (on H[j]). This runs in O(logi) time.

Assume the heap currently has n elements. After deleting the element H[i] the heap will have only n-1 elements, and heap order may be violated. We can fix heap order by using the heapify-down algorithm. The first step is to move the element in the last position to position i to fix the “hole” left by the removal of the ith element. If the new key is too small, then heapify-up can fix it. If it's too big, heapify-down swaps the ith element with the smaller of its children, and then moves recursively until the heap order is reestablished or it reaches the end of the heap. This runs in O(logn) time.

Implementing Priority Queues with Heaps:

• StartHeap(N) - returns an empty heap H that can store at most N elements (O(N) time)
• Insert(H,v) - inserts item v into heap H (O(logn) time)
• FindMin(H) - identifies the minimum element of heap H (O(1) time)
• Delete(H,i) - deletes the element in heap position i (O(logn) time)
• ExtractMin(H) - identifies and deletes an element with minimum key value from heap H (O(logn) time)

I think this section was very useful in solidifying the lectures. I understand what's going on in class, but sometimes it is hard to see what's going on because our class time is so short. It's nice to read everything all at once to see how it all works together. I'd rate this section a 10!