堆与优先队列
Binary Heap
堆是一个很重要的数据结构;它是绝大多数优先队列 (priority queue) 的内部实现;其诞生也使得
Complete Binary Tree
A binary tree is composed by recursively following the principles:
- It is empty.
- It is a node with links to left and right binary trees.
Complete tree. Perfectly balanced, except for bottom level.
An important property. Height of the complete binary tree with
Heap Properties
A binary heap is a complete binary tree with the following properties:
- Largest key is
a[1], which is the root of binary tree. - Parent's key NO smaller than children's keys.
We often use arrays to represent a heap, it is simple and do not require explicit links.
- Indices start at
. - Take nodes in level order.
- Can use array indices to move through tree.
- Parent of node at
kisk/2. - Children of node at
kare at2kand2k+1.
- Parent of node at
Promotion and Insertion
Promotion is needed when child's key becomes larger key than its parent's key.
Promotion follows Peter Principle: Node promoted to level of incompetence.
private void swim(int k) {
while (k > 1 && less(k / 2, k)) {
exch(k, k / 2);
k /= 2;
}
}
This allows us to insert new nodes into a heap; We just add the node at end, then swim it up. It will cost at most
public void insert(Key x) {
pq[++N] = x;
swim(N);
}
Demotion and Deletion
Demotion is needed when parent's key becomes smaller than one (or both) of its children's.
Demotion shows power struggle: Better subordinate gets promoted.
private void sink(int k) { // top-down reheapify
while (2 * k <= N) {
int j = 2 * k;
if (j < N && less(j, j + 1)) ++j;
if (!less(k, j)) break;
exch(k, j);
k = j;
}
}
This allows us to delete the root (maximum) in a heap; We exchange root with the node at end, then sink it down. It will cost at most
public Key delMax() {
Key max = pq[1];
exch(1, N--);
sink(1);
pq[N + 1] = null; // prevent loitering
return max;
}
Construction
A trivial way to build a heap given
In fact, there is a bottom-up linear-time method to construct a heap out of
For a node with links to left subheap and right subheap, we heapify the node by sinking it down. Therefore, from the last second level, we heapify the nodes level by level.
The reason why we start from the last second level is that every single node is a subheap of size
// Note that it is a 1-based indexing
for (int k = N/2; k >= 1; --k)
sink(a, k, N);
// Reverse traverse: We could heapify a node only if its two sons are both heaps
Proposition. Bottom-up heap construction uses (linear)
Assume
Heap Sort
The basic plan for in-place heap sort.
- Construct a max-heap with all
keys. (linear-time bottom-up heap construction) - Repeatedly remove the maximum key. (linearithmic-time sorting down process)
See the complete Java code below:
public class Heap {
public static void sort(Comparable[] a) {
int N = a.length;
for (int k = N/2; k >= 1; --k) // construction
sink(a, k, N);
while (N > 1) { // sorting down
exch(a, 1, N);
sink(a, 1, --N); // Leave in array instead of nulling out
}
}
private static void sink(Comparable[] a, int k, int N) { /* as before */ }
private static boolean less(Comparable[] a, int i, int j) { /* as before */ }
private static void exch(Comparable[] a, int i, int j) { /* as before */ }
}
Proposition. Heapsort uses (linearithmic)
The significance of heap sort. In-place sorting algorithm with
- Mergesort: no, linear extra space. (in-place merge possible with high constants, not pratical)
- Quicksort: no, quadratic time in worst case.
- Heapsort: yes! Optimal in both time and space.
However, there is still an unpratical bottom line for heap sort.
- Inner loop longer than quicksort's.
- Makes poor use of cache memory.
- Not stable.
Priority Queues
We've introduced several collections. They all support insert and delete items. What differs them is the item to delete:
- Stack. Remove the item most recently added.
- Queue. Remove the item least recently added.
- Double-ended queue. Remove the item most or least recently added.
- Priority queue. Remove the largest (or smallest) item.
There are two kinds of PQs: elementary PQs (implemented with linked lists or resizing arrays) and heap-based PQs. See the order of growth of running time for PQs with
| implementation | insert | del max | max |
|---|---|---|---|
| (elementary) unordered array | |||
| (elementary) ordered array | |||
| binary heap |
It's natural and efficient to implement PQs with heap. See the complete Java code below:
public class MaxPQ<Key> implements Iterable<Key> {
private Key[] pq;
private int n;
private Comparator<Key> comparator;
/*
Constructors
*/
public MaxPQ(int initCapacity) {
pq = (Key[]) new Object[initCapacity + 1];
n = 0;
}
public MaxPQ() { this(1); }
public MaxPQ(int initCapacity, Comparator<Key> comparator) {
this.comparator = comparator;
pq = (Key[]) new Object[initCapacity + 1];
n = 0;
}
public MaxPQ(Comparator<Key> comparator) { this(1, comparator); }
// Construct the heap using O(N) bottom-up method
public MaxPQ(Key[] keys) {
n = keys.length;
pq = (Key[]) new Object[keys.length + 1];
for (int i = 0; i < n; ++i) pq[i + 1] = keys[i];
for (int k = n/2; k >= 1; --k) sink(k);
assert isMaxHeap();
}
/*
Priority Queue API (except resize)
*/
public boolean isEmpty() { return n == 0; }
public int size() { return n; }
public Key max() {
if (isEmpty()) throw new NoSuchElementException("Priority Queue Underflow");
return pq[1];
}
private void resize(int capacity) { // resizing heap
assert capacity > n;
Key[] temp = (Key[]) new Object[capacity];
for (int i = 1; i <= n; ++i) temp[i] = pq[i];
pq = temp;
}
public void insert(Key x) {
if (n == pq.length - 1) resize(2 * pq.length);
pq[++n] = x;
swim(n);
assert isMaxHeap();
}
public Key delMax() {
if (isEmpty()) throw new NoSuchElementException("Priority Queue Underflow");
Key max = pq[1];
exch(1, n--);
sink(1);
pq[n + 1] = null;
if ((n > 0) && (n == (pq.length - 1) / 4)) resize(pq.length / 2);
assert isMaxHeap();
return max;
}
/*
Helper functions to restore the heap invariant
*/
private void swim(int k) {
while (k > 1 && less(k/2, k)) {
exch(k/2, k);
k /= 2;
}
}
private void sink(int k) {
while (2*k <= n) {
int j = 2*k;
if (j < n && less(j, j+1)) ++j;
if (!less(k, j)) break;
exch(k, j);
k = j;
}
}
/*
Helper functions for compares and swaps.
*/
private boolean less(int i, int j) {
if (comparator == null) {
return ((Comparable<Key>) pq[i]).compareTo(pq[j]) < 0;
} else {
return comparator.compare(pq[i], pq[j]) < 0;
}
}
private void exch(int i, int j) {
Key swap = pq[i]; pq[i] = pq[j]; pq[j] = swap;
}
private boolean isMaxHeap() {
for (int i = 1; i <= n; ++i) {
if (pq[i] == null) return false;
}
for (int i = n+1; i < pq.length; ++i) {
if (pq[i] != null) return false;
}
if (pq[0] != null) return false;
return isMaxHeapOrdered(1);
}
private boolean isMaxHeapOrdered(int k) {
if (k > n) return true;
int left = 2*k;
int right = 2*k + 1;
if (left <= n && less(k, left)) return false;
if (left <= n && less(k, right)) return false;
return isMaxHeapOrdered(left) && isMaxHeapOrdered(right);
}
/*
Iterator
*/
public Iterator<Key> iterator() { return new HeapIterator(); }
private class HeapIterator implements Iterator<Key> {
private MaxPQ<Key> copy;
// copy the heap to avoid external mutation in next()
public HeapIterator() {
if (comparator == null) copy = new MaxPQ<Key>(size());
else copy = new MaxPQ<Key>(size(), comparator);
for (int i = 1; i <= n; ++i) MaxPQ.insert(pq[i]);
}
public boolean HasNext() { return !copy.isEmpty(); }
public void remove() { throw new UnsupportedOperationException(); }
public Key next() {
if (!hasNext()) throw new NoSuchElementException();
return copy.delMax();
}
}
/*
Unit test (optional)
*/
public static void main(String[] args) {
...
}
}
