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:
This section was interesting and helped me learn the runtimes of the heap much better. 10/10.