Priority Queues (Heaps)

当任务提交给打印机时，通常会生成一个队列。但如果某些任务特别重要的时候，这显然是不合适的，我们希望它一到就立刻执行。类似的在一个多用户的系统中，操作系统需要决定先执行哪些进程。这些应用需要一种特定的队列，通常称为优先队列。

Model

优先队列至少有两种操作，insert和deleteMin，类似于普通队列的出队和入队。有很多种实现优先队列的方式，这里我们将常用二分堆的方式，通常也直接称之为堆（Heap）。类似于二分查找树，堆有两种属性，结构特性和堆特性。像AVL树一样，某些操作是可以破坏其中一个特性，因此堆需要修复所有特性后才能停止操作。

Structure Property

堆是一种完全二叉树，完全二叉树当高度为h时，会有2^h到2^h+1 - 1个节点。也意味着堆的高度是LogN。由于完全二叉树的特性，完全可以将它存储在一个数组中也不需要链接。
对于数组中任意位置i，左孩子位置为2i，右孩子位置为2i+1，父节点则为。

Heap-Order Propery

堆的特性则支持我们能够快速的执行某些操作，例如我们需要快速的获得最小值，显而易见最小的元素应该是根节点。我们假设所有的子树都是一个堆，因此所有的节点都应该小于它的子孙节点。
因此，在一个堆中，对于所有的节点X，X的所有父节点都小于或者等于X（不包括根节点，因为根节点没有父节点）。这样的话最小的节点就在根节点，我们可以在常量时间完成findMin操作。

Basic Heap Operations

一个堆的结构可以表示为：

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到堆中，我们需要在下一个可用的位置创建一个孔，保持堆的完全性。如果X不违反堆的顺序，我们就用X替换这个孔，然后完成操作。否则，我们就将这个孔向着它的父节点进行滑动，直到X可以被插入或者到根节点。
这种方法通常称为渗透，新的元素不断找寻对的位置从而渗透到堆中。

deleteMin

找到最小的元素时容易的，问题是如何删除它。当最小的元素被删除时，根节点将会变为一个孔。由于现在对少了一个元素，因此最后一个元素X就必须被移动。如果X可以被移动到这个孔上，操作就结束。我们需要将孔的孩子节点移动这个孔上，然后不断的下沉这个孔。重复这个操作直到X可以替换这个孔。