堆与优先队列

Binary Heap

堆是一个很重要的数据结构;它是绝大多数优先队列 (priority queue) 的内部实现;其诞生也使得 ∼Nlog⁡N\sim N\log{N} 的 in-place 排序算法成为可能。(堆排序) 但是堆排序仍然无法在日常应用中代替快速排序;它常常需要访问相距较远的地址取值,使得其底层的效率较为低下。

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.

Note that the bottom level is NOT balanced

An important property. Height of the complete binary tree with NN nodes is ⌊lg⁡N⌋\lfloor \lg{N} \rfloor.

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 11.
  • Take nodes in level order.
  • Can use array indices to move through tree.
    • Parent of node at k is k/2.
    • Children of node at k are at 2k and 2k+1.

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.

java
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 1+lg⁡N1+\lg{N} compares.

java
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.

java
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 2lg⁡N2\lg N compares.

java
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 NN keys is to insert them one by one into an empty heap. However, this will cost ∼Nlog⁡N\sim N\log{N} compares and exchanges.

In fact, there is a bottom-up linear-time method to construct a heap out of NN keys.

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 11.

java
// 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) ≤2N\leq 2N compares and exchanges.

Assume SS is the total number of compares and exchanges. Note that the number of compares and exchanges when heapifying (sinking down) a node is proportional to the its height hh.

S=20h+21(h−1)+22(h−2)+...+2k(h−k)+...+2h−1=2h+1−h−2S=2^0h+2^1(h-1)+2^2(h-2)+...+2^k(h-k)+...+2^{h-1}=2^{h+1}-h-2. The height of heap is h=log⁡nh=\log{n}, thus S=∼NS=\sim N.

Heap Sort

The basic plan for in-place heap sort.

  • Construct a max-heap with all NN keys. (linear-time bottom-up heap construction)
  • Repeatedly remove the maximum key. (linearithmic-time sorting down process)

See the complete Java code below:

java
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) ≤2Nlg⁡N\leq 2N\lg{N} compares and exchanges.

The significance of heap sort. In-place sorting algorithm with Nlog⁡NN\log{N} worst-case.

  • 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 NN items:

implementation insert del max max
(elementary) unordered array 11 NN NN
(elementary) ordered array NN 11 11
binary heap log⁡N\log{N} log⁡N\log{N} log⁡N\log{N}

It's natural and efficient to implement PQs with heap. See the complete Java code below:

java
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) {
        ...
    }
}
CC BY-NC-SA 4.0
正在加载评论…