Heap（Priority Queue）

优先队列（Priority Queue）是一种非常重要的数据结构，本文将讨论对于优先队列的有效实现以及优先队列的使用。一般来说，优先队列一定具有两个基本操作：插入Insert和删除最小DeleteMin。

Basic Implementation

最简单的实现是简单链表（LinkedList），在链表头或者尾插入元素（O(1)），再遍历链表找到最小元素并删除（O(N)）。或者一直保持链表排序（O(N)），这样删除最小只用花费（O(1)）。

另一种实现方式是查找二叉树（Binary Search Tree）。插入是随机的，花费O(logN)的时间，删除最小则一直删除最左边的元素（O(logN)），如上时间花费都是平均时间。由于最小元素一直被删除，树的结构将被影响（最坏情况下树的深度将是其期望深度的两倍）。

Heap

堆（Heap）能够在O(logN)的时间内将如上两个操作完成。

堆具有结构性与堆序性两个性质，而对于堆的任意插入（Insert）和删除最小（DeleteMin）都可能破坏这两个性质。因此，我们所有对堆的操作都要维持这两个操作。

结构性

堆的结构是一棵Complete Binary Tree，意味着堆是个完全填满的二叉树（底层由左往右插入元素，可以不满），其高（height）为logN。因为完全二叉树的规律，我们不需要使用链表实现堆，而可以用一个普通数组实现它。对于任意在i上的元素，左儿子是2i，右儿子是2i+1，母亲是i/2

堆序性

为了快速实现DeleteMin这一操作，我们应当始终确保最小元素在根（Root）的位置上。我们应当确保任意结点都小于他的孩子。

Heap Operations

如上文所说，优先队列（堆）有两个基本操作：Insert和DeleteMin，我们将在下文中探讨如何实现这两个基本操作。

Insert

将插入元素插入到堆的下一个位置中（末尾指针处），如果堆的堆序性没有被破坏，那么插入完成。
如果堆的堆序性被破坏，我们交换该元素与其父节点。重复这一过程，一直到堆序性没有被破坏为止。

这一过程被称作Percolate Up。

public void insert(AnyType x) 
{
  if(currentSize == array.length - 1) 
  {
    enlargeArray(array.length * 2 + 1);
  }

  int hole = currentSize++;
  for(array[0] = x; x.compareTo(array[hole]) < 0; hole/=2) 
  {
    array[hole] = array[hole/2]; //将swap需要3步的操作化简为1步
  }
  array[hole] = x;
}

最坏情况：插入元素是最小值(O(logN))

DeleteMin

public AnyType deleteMin() 
{
  if(isEmpty()) 
    throw new UnderflowException();

  AnyType min = findMin();
  array[1] = array[currentSize--];
  percolateDown(1);

  return min;
}

public void percolateDown(int hole) 
{
  int child;
  AnyType tmp = array[hole];

  for(; hole * 2 <= currentSize; hole = child) {
    child = hole * 2;
    if(child != currentSize && array[child + 1].compareTo(array[child]) < 0) {
      child++;
    } //ensure we use smaller child for later comparison

    if(array[child].compareTo(tmp) < 0) 
    {
      array[hole] = array[child];//swap a[hole] and a[child]
    } else {
      break;
    }
  }
  array[hole] = tmp;
}