二叉堆（优先队列）

定义

二叉堆是具有结构性质和堆序性质的一棵完全二叉树；
完全二叉树：
二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数(即1~h-1层为一个满二叉树)，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。

一颗完全二叉树

结构性质：
一颗完全二叉树可以用一个数组表示而不需要使用链；对于数组(下标从0开始)中任一位置i上的元素，其左儿子在位置2i+1上，右儿子在位置2i+2上，父亲在位置

\left \lfloor (i-1)/2\right \rfloor

上。

完全二叉树的数组表示

为了便于寻找父节点和子节点，数组下标从1开始，则对于数组中任一位置i上的元素，其左儿子在位置2i上，右儿子在位置2i+1上，父亲在位置 $\left \lfloor i/2\right \rfloor$ 上。

完全二叉树的数组表示

堆序性质：
最小堆的堆序性质为任一节点的值小于其所有儿子节点的值；最大堆的堆序性质为任一节点的值大于其所有儿子节点的值。

最小堆

堆的基本操作

以上面的最小堆为例说明。
insert（插入）
为了将一个元素X插入到堆中，我们在下一个可用位置创建一个空穴（否则该堆就不再是完全二叉树）。如果X可以放在该空穴中而不破坏堆的堆序性质，那么插入完成。否则，我们把空穴的父节点上的元素移入该空穴中，这样，空穴就朝着根的方向上冒一步。继续改过程，直到X能够被放入空穴中。这种一般的操作叫做上滤(percolate up)，如下图所示：尝试在前面的最小堆中插入元素14。

上滤（percolate up）

插入代码如下：

    public void insert(AnyType x) {
        if (isFull()) {
            enlargeArray(array.length * 2 + 1);
        }
        // percolate up
        int hole = ++currentSize;
        for (; hole > 1 && x.compareTo(array[hole / 2]) < 0; hole /= 2) {
            array[hole] = array[hole / 2];
        }
        array[hole] = x;
    }

插入操作分析：
如果欲插入的元素从一直上滤到根处，那么这种插入的时间达到最坏情况O(logN)。平均情况，上滤终止得要早，业已证明，执行一次插入平均需要上移1.607层，所以平均情况下，插入操作可以视为O(1)的时间复杂度。
deleteMin（删除最小元）
删除最小元，即删除堆的根节点。删除根节点之后，根节点成了一个空穴。为了保证删除该元素后，堆仍然是一颗完全二叉树，末尾元素必须移动到该堆的某个位置。如果末尾元素可以被放到空穴中，而不破坏堆序性质，那么deleteMin完成。不过这一般不太可能，因此我们将空穴的两个儿子中较小者移入空穴，这样就把空穴向下推了一层。重复该步骤直到末尾元素可以被放入到空穴中为止。也因此可以得出结论，末尾元素最后必定被移动到从根开始包含最小儿子的一条路径上的某个正确位置。这种一般的策略叫做下滤（percolate down），如下图所示：删除堆的最小元素13。

下滤（percolate down）

删除最小元代码如下：

public AnyType deleteMin() {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }
        AnyType minItem = findMin();
        array[1] = array[currentSize];
        array[currentSize--] = null;
        percolateDown(1);
        return minItem;
}

  /**
   * 堆内元素向下移动
   * @param hole 下移的开始下标
   */
private 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++;
            }
            if (array[child].compareTo(tmp) < 0) {
                array[hole] = array[child];
            } else {
                break;
            }
        }
        array[hole] = tmp;
}

删除最小元分析：
删除最小元的操作的最坏情形运行时间为O(logN)。平均而言，被放到根处的元素几乎下滤到堆的底层（即它所来自的那层），因此平均运行时间也为O(logN)。
buildHeap（构建堆）
二叉堆的构建一般分为两种。第一种可以由N个相继的insert操作完成，每个insert操作花费的平均时间为O(1)，所以这种方法的总的运行时间平均为O(N)；第二种是将N项以任意顺序放入树中，保持结构特性。然后，对所有的非叶子节点进行下滤操作。这里操作的顺序特别重要：从最后一个非叶子节点开始，倒序，到根节点为止（图中即为从右到左从下到上的顺序）。第二种方法的操作被称为堆化。这种方法的运行时间为O(N)，通过计算堆中所有节点的高度的和来得到，这里不给出证明。下面给出图示：

代码如下：

    // 构造器：以数组作为参数
    public BinaryHeap(AnyType[] items) {
        currentSize = items.length;
        array = (AnyType[]) new Comparable[(currentSize + 2) * 11 / 10];
        int i = 1;
        for (AnyType item : items) {
            array[i++] = item;
        }
        buildHeap();
    }

    /**
     * 从任意排列的项目中建立堆，线性时间运行
     */
    private void buildHeap() {
        for (int i = currentSize / 2; i > 0; i--) {
            percolateDown(i);
        }
    }

其他堆操作
decreaseKey（降低关键字的值）
$decreaseKey(p,\Delta )$ 操作降低在位置p处的值，降值的幅度为正的量 $\Delta$ 。由于这可能破坏堆序性质，因此必须进行上滤操作对堆进行调整。该操作对系统管理员是有用的：系统管理员能够使他们的程序以最高的优先级来运行。
increaseKey（增加关键字的值）
$increaseKey(p,\Delta )$ 操作增加在位置p处的值，增加的幅度为正的量 $\Delta$ 。由于这可能破坏堆序性质，因此必须进行下滤操作对堆进行调整。许多调度程序自动降低正在过多消耗CPU时间的进程的优先级。
delete（删除）
delete(p)删除堆中位置p上的节点。该操作通过首先执行 $decraseKey(p,\infty )$ ，然后执行deleteMin操作来完成。当一个进程被用户中止时，它必须从优先队列中除去。

二叉堆的完整程序

public class BinaryHeap<AnyType extends Comparable<? super AnyType>> {

    private static final int DEFAULT_CAPACITY = 10;// 默认容量
    private int currentSize; // 当前堆大小
    private AnyType[] array; // 数组

    public BinaryHeap() {
        this(DEFAULT_CAPACITY);
    }

    public BinaryHeap(int capacity) {
        currentSize = 0;
        array = (AnyType[]) new Comparable[capacity + 1];
    }

    public BinaryHeap(AnyType[] items) {
        currentSize = items.length;
        array = (AnyType[]) new Comparable[(currentSize + 2) * 11 / 10];
        int i = 1;
        for (AnyType item : items) {
            array[i++] = item;
        }
        buildHeap();
    }

    /**
     * 从任意排列的项目中建立堆，线性时间运行
     */
    private void buildHeap() {
        for (int i = currentSize / 2; i > 0; i--) {
            percolateDown(i);
        }
    }

    /**
     * 堆内元素向下移动
     * @param hole 下移的开始下标
     */
    private 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++;
            }

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

    /**
     * 插入一个元素
     * @param x 插入元素
     */
    public void insert(AnyType x) {
        if (isFull()) {
            enlargeArray(array.length * 2 + 1);
        }
        int hole = ++currentSize;
        for (; hole > 1 && x.compareTo(array[hole / 2]) < 0; hole /= 2) {
            array[hole] = array[hole / 2];
        }
        array[hole] = x;
    }

    /**
     * 堆是否满
     * @return 是否堆满
     */
    public boolean isFull() {
        return currentSize == array.length - 1;
    }

    /**
     * 堆是否空
     * @return 是否堆空
     */
    public boolean isEmpty() {
        return currentSize == 0;
    }

    /**
     * 清空堆
     */
    @SuppressWarnings("unused")
    public void makeEmpay() {
        currentSize = 0;
        for (AnyType anyType : array) {
            anyType = null;
        }
    }

    /**
     * 找到堆中最小元素
     * @return 最小元素
     */
    public AnyType findMin() {
        if (isEmpty())
            return null;
        return array[1];
    }

    /**
     * 删除堆中最小元素
     * @return 删除元素
     */
    public AnyType deleteMin() {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }
        AnyType minItem = findMin();
        array[1] = array[currentSize];
        array[currentSize--] = null;
        percolateDown(1);
        return minItem;
    }

    /**
     * 扩大数组容量
     * @param newSize 新的容量
     */
    @SuppressWarnings("unchecked")
    private void enlargeArray(int newSize) {
        AnyType[] old = array;
        array = (AnyType[]) new Comparable[newSize];
        for (int i = 0; i < old.length; i++) {
            array[i] = old[i];
        }
    }

    /**
     * 输出数组中的元素
     */
    public void printHeap() {
        for (AnyType anyType : array) {
            System.out.print(anyType + " ");
        }
    }
    
}

JDK中的优先队列简介

PriorityQueue 是基于堆实现的无界优先级队列。优先级队列中的元素顺序根据元素的自然序或者构造器中提供的 Comparator。不允许 null 元素，不允许插入不可比较的元素(未实现 Comparable)。它不保证线程安全，JDK 也提供了线程安全的优先级队列 PriorityBlockingQueue。
初始化操作
PriorityQueue 的构造函数有 7 个，可以分为两类，提供初始元素和不提供初始元素。提供初始元素的构造器中，PriorityQueue 可以直接根据 SortedSet ， PriorityQueue ，任意 Collection（需要堆化）来构造堆。举例：

        List<Integer> numList = Arrays.asList(12, 5, 20, 7, 33, 1);
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<Integer>(numList);

入队操作
add和offer。在队尾添加一个元素（判断是否需要扩容），并通过上滤操作（shiftUp）保证堆序结构。

priorityQueue.add(6);

出队操作
poll。将堆的根元素出队，并进行下滤操作（shiftDown）保证堆序结构。

// 1
priorityQueue.poll();