當(dāng)任務(wù)提交給打印機時，通常會生成一個隊列。但如果某些任務(wù)特別重要的時候，這顯然是不合適的，我們希望它一到就立刻執(zhí)行。類似的在一個多用戶的系統(tǒng)中，操作系統(tǒng)需要決定先執(zhí)行哪些進(jìn)程。這些應(yīng)用需要一種特定的隊列，通常稱為優(yōu)先隊列。

Model

優(yōu)先隊列至少有兩種操作，insert和deleteMin，類似于普通隊列的出隊和入隊。有很多種實現(xiàn)優(yōu)先隊列的方式，這里我們將常用二分堆的方式，通常也直接稱之為堆（Heap）。類似于二分查找樹，堆有兩種屬性，結(jié)構(gòu)特性和堆特性。像AVL樹一樣，某些操作是可以破壞其中一個特性，因此堆需要修復(fù)所有特性后才能停止操作。

Structure Property

堆是一種完全二叉樹，完全二叉樹當(dāng)高度為h時，會有2^h到2^h+1 - 1個節(jié)點。也意味著堆的高度是LogN。由于完全二叉樹的特性，完全可以將它存儲在一個數(shù)組中也不需要鏈接。
對于數(shù)組中任意位置i，左孩子位置為2i，右孩子位置為2i+1，父節(jié)點則為。

Heap-Order Propery

堆的特性則支持我們能夠快速的執(zhí)行某些操作，例如我們需要快速的獲得最小值，顯而易見最小的元素應(yīng)該是根節(jié)點。我們假設(shè)所有的子樹都是一個堆，因此所有的節(jié)點都應(yīng)該小于它的子孫節(jié)點。
因此，在一個堆中，對于所有的節(jié)點X，X的所有父節(jié)點都小于或者等于X（不包括根節(jié)點，因為根節(jié)點沒有父節(jié)點）。這樣的話最小的節(jié)點就在根節(jié)點，我們可以在常量時間完成findMin操作。

Basic Heap Operations

一個堆的結(jié)構(gòu)可以表示為：

import java.nio.BufferUnderflowException;

/**
 * @author dalu
 * @create 2020-04-15 22:22
 */
public class BinaryHeap <AnyType extends Comparable<? super AnyType>> {
    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();

    }

    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 / 2]) < 0; hole /= 2) {
            array[hole] = array[hole / 2];
        }
        array[hole] = x;

    }

    public AnyType findMin() {
        if(isEmpty()) {
            throw new BufferUnderflowException();
        }
        return  array[1];

    }

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

    public boolean isEmpty() {
        return (currentSize == 0);

    }

    public void makeEmpty() {
        currentSize = 0;
    }

    private static final int DEFAULT_CAPACITY = 10;

    private int currentSize;
    private AnyType[] array;

    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;
    }

    private void buildHeap() {
        for(int i = currentSize / 2; i > 0; i--) {
            percolateDown(i);
        }
    }

    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];
        }

    }
}

insert

插入一個元素X到堆中，我們需要在下一個可用的位置創(chuàng)建一個孔，保持堆的完全性。如果X不違反堆的順序，我們就用X替換這個孔，然后完成操作。否則，我們就將這個孔向著它的父節(jié)點進(jìn)行滑動，直到X可以被插入或者到根節(jié)點。
這種方法通常稱為滲透，新的元素不斷找尋對的位置從而滲透到堆中。

deleteMin

找到最小的元素時容易的，問題是如何刪除它。當(dāng)最小的元素被刪除時，根節(jié)點將會變?yōu)橐粋€孔。由于現(xiàn)在對少了一個元素，因此最后一個元素X就必須被移動。如果X可以被移動到這個孔上，操作就結(jié)束。我們需要將孔的孩子節(jié)點移動這個孔上，然后不斷的下沉這個孔。重復(fù)這個操作直到X可以替換這個孔。