Priority Queues

Priority Queues#

A Priority Queue (PQ) is an Abstract Data Type (ADT) that stores a collection of items, where each item consists of an element and an associated priority. The priority is typically a number, but it can be any value that allows for ordering.

The two fundamental operations of a (min) priority queue are:

insert(p, e): Inserts an element e with priority p into the PQ.
removeMin(): Removes and returns the element with the smallest priority.

Sometimes, other operations like changePriority(p, e) (modifies an element’s priority) and remove(e) (removes a specific element) are also included.

Simple PQ Implementations#

Here’s a comparison of simple list- and array-based implementations:

	Unsorted List/Array	Sorted List/Array
`insert(p, e)`	\(O(1)\)	\(O(n)\)
`removeMin()`	\(O(n)\)	\(O(1)\)

To do better, we need a data structure that can perform both insert and removeMin operations more efficiently than \(O(n)\). This is where the heap comes in.

The Heap Data Structure#

A heap is a binary tree-based data structure that is ideal for implementing priority queues. It is defined by two main properties:

Structural Property (Completeness): A heap is a complete binary tree. This means all levels of the tree are completely filled, except possibly the last level, which is filled from left to right.
Heap Property (Order): In a min-heap, the priority of any node is less than or equal to the priorities of its children. This ensures that the node with the minimum priority is always at the root of the tree.

The completeness property is crucial because it guarantees the tree is as “bushy” and short as possible. The height of a complete binary tree with \(n\) nodes is always \(O(\log n)\). If we can design our operations to run in time proportional to the tree’s height, we can achieve \(O(\log n)\) performance for both insert and removeMin.

Array-Based Implementation#

Because a heap is a complete binary tree, it can be stored perfectly in an array with no wasted space. We can easily find the parent and children of any node at index i (using 0-based indexing):

Parent: (i - 1) // 2
Left Child: 2*i + 1
Right Child: 2*i + 2

Core Heap Operations#

All heap operations must maintain both the completeness and heap properties.

Insert (amortized \(O(\log n)\))#

To insert a new item while maintaining completeness, we add it to the first available space in the array (which corresponds to the next open leaf in the tree).

Add the new element to the end of the array.
This may violate the heap property. To fix it, we bubble up the new element.
Compare the new element with its parent. If the new element’s priority is smaller, swap them.
Repeat this process—swapping the element with its parent—until it reaches a position where its priority is greater than or equal to its parent’s priority, or until it becomes the root.

This process takes at most \(O(\log n)\) time because the path from a leaf to the root is equal to the tree’s height.

If the insertion requires a bigger array, we make a new one twice as big, move everything over, and proceed - this makes the analysis an amortized one.

Remove Minimum (\(O(\log n)\))#

The minimum element is always at the root (index 0).

Save the root element to be returned later.
To fill the “hole” at the root and maintain completeness, move the last element in the array to the root.
This move almost certainly violates the heap property at the root. To fix it, we bubble down (or “down-heap”) the new root.
Compare the element with its children. Swap it with its smaller child.
Repeat this process—swapping the element with its smaller child—until it reaches a position where its priority is less than or equal to the priorities of its children, or until it becomes a leaf.

This process also takes \(O(\log n)\) time, as it follows a path from the root down to a leaf.

	Unsorted List/Array	Sorted List/Array	Heap
`insert(p, e)`	\(O(1)\)	\(O(n)\)	amortized \(O(\log(n))\)
`removeMin()`	\(O(n)\)	\(O(1)\)	\(O(\log(n))\)

Heap Sort#

Using a heap, we can create a powerful sorting algorithm called Heap Sort.

Conceptual Heap Sort (\(O(n \log n)\))#

This is the most straightforward “PQ Sort” using a heap:

Build Heap: Insert all \(n\) elements into a new heap. This takes \(n\) insert operations, for a total time of \(n \times O(\log n) = O(n \log n)\).
Extract All: Call removeMin \(n\) times to pull the elements out in sorted order. This takes \(n\) removeMin operations, for a total time of \(n \times O(\log n) = O(n \log n)\).

The total time is \(O(n \log n) + O(n \log n)\), which simplifies to \(O(n \log n)\). This is significantly faster than the \(O(n^2)\) performance of sorting algorithms like Selection Sort, Insertion Sort, or Bubble Sort.

Optimization: Bottom-Up Heap Construction (\(O(n)\))#

If we have all \(n\) elements at the start, we can build the heap much faster than \(O(n \log n)\). This “bottom-up heapify” algorithm works in linear \(O(n)\) time.

Start with the \(n\) elements already in an array, viewing them as a complete (but unordered) binary tree.
We only need to fix the nodes that are not leaves. The last non-leaf node is at index (n/2) - 1.
Iterate backwards from the last non-leaf node down to the root (index 0).
At each node, perform a bubble-down operation to fix the heap property for the subtree rooted at that node.

Analysis: Why is this \(O(n)\)?

About \(n/2\) nodes are leaves and require 0 work.
About \(n/4\) nodes are one level up and require at most 1 swap each.
About \(n/8\) nodes are two levels up and require at most 2 swaps each.
…
The single root node requires at most \(O(\log n)\) swaps.

The total work is the sum \(S = \sum_{i=0}^{\lfloor\log n\rfloor} i \cdot \frac{n}{2^{i+1}}\) (where \(i\) is the height from the bottom). This can be rewritten as \(n \sum i(\frac{1}{2})^{i+1}\). This mathematical series converges to a constant (it approaches 1 as \(n\) grows). Therefore, the total time for bottom-up heap construction is \(O(n \cdot 1) = O(n)\).

In-Place Heap Sort#

We can combine these ideas to perform Heap Sort in-place (using \(O(1)\) extra space).

So far we’ve been using a min-heap. To get a forward-sorted (increasing) array, we use a Max-Heap (where the parent’s priority is greater than its children’s).

Step 1: Build Max-Heap (\(O(n)\))
- Take the input array and use the \(O(n)\) bottom-up heapify algorithm to turn it into a max-heap. The largest element is now at the root (array[0]).
Step 2: Sort-Down (\(O(n \log n)\))
- We will partition the array into a heap portion (at the front) and a sorted portion (at the end).
- Repeat \(n-1\) times: a. Swap: Swap the root element (array[0], the largest remaining item) with the last element in the heap portion. b. Shrink Heap: The largest item is now in its correct, final sorted position. Decrement the size of the heap portion by 1. c. Fix Heap: The new root (which came from the end) is out of place. Bubble it down to restore the max-heap property within the smaller heap.

This process systematically moves the largest, then second-largest, then third-largest element to the end of the array, resulting in a fully sorted array in \(O(n \log n)\) time with no extra space.