队也叫做优先级队列。队列是一种先进先出的数据结构，有的时候，要操作的数据有优先级，需要优先级高的先出队列，就是这样的数据结构。堆的数据结构提供了两个最基本的操作：返回最高级优先级对象和添加新的对象。堆实际上是一种在完全二叉树的基础上进行元素的调整。

1、堆基本概念

如果有一个集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储 在一 个一维数组中，并满足：Ki = K2i+1 且 Ki >= K2i+2) i = 0，1，2…，则称为 小堆(或大 堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

堆的性质：1，堆总是一颗完全二叉树。2，堆中的某个节点的值总是不大于或不小于其父亲节点的值。这里就是指大根堆或小根堆。

堆是一颗使用数组来存储的完全二叉树，整个的遍历过程使用了层序遍历。和二叉树相比，堆是线性顺序存储的，但是在画图理解的时候，我们画成完全二叉树的形式。

2、堆的创建

关于堆的创建，需要用到堆的向下调整。因为堆是把元素存在数组中的，如果我们假设i为节点在数组中的下标，那么根据完全二叉树的性质，i是被称为父亲节点的话：

（1）如果i为0，则i表示的节点为根节点，否则i节点的双亲节点为 (i - 1)/2；

（2）如果2 * i + 1 小于节点个数，则节点i的左孩子下标为2 * i + 1，否则没有孩子；

（3）如果2 * i + 2 小于节点个数，则节点i的右孩子下标为2 * i + 2，否则没有孩子。

这个在后面堆的创建中需要用到，下面我们以建立大堆为例。堆（优先级队列）的存储数据的方式是使用数组来存储的，先定义好数组和有效数组的大小。

class TestHeap {    public int[] elem;    public int usedSize;    public TestHeap(int[] elem) {        this.elem = new int[10];    }}

然后把要建立堆的数组进行拷贝。也可以不拷贝，直接使用。拷贝好之后，从什么地方开始调整？这就需要画图来看一看。把使用数组存储的数据画成完全二叉树的形式后，发现：

直接从0下标开始的话，调整起来不方便。所以从尾节点对应的父节点开始，一步一步调整，一直到0下标。以9下标为例，它的父节点是4下标，是整个数组有效长度的一半。所以调整要从整个数组有效长度的一半开始调整。使用createHeap方法。

class TestHeap {    public int[] elem;    public int usedSize;    public TestHeap(int[] elem) {        this.elem = new int[10];    }    //建堆    public void createHeap(int[] array) {        //拷贝过程        for (int i = 0; i < array.length; i++) {            this.elem[i] = array[i];            ++this.usedSize;        }        //开始调整过程        for (int p = (usedSize - 1 - 1) >>> 1; p >= 0; p--) {            shiftDown(p, usedSize);        }    }}

调整的过程使用一个shiftDown方法，传进去这个下标和数组的有效长度。

shiftDown方法

这个方法就是具体的调整方法。为了方便，我们定义parent和child变量。其中，parent就是父亲节点，child就是父亲节点对应的孩子节点，有左右孩子之分。他们的关系需要用到前面的性质。其实从图上就能看出来，以3号下标为例，它的左右孩子下标就是7和8。对于左孩子来说，和父节点的下标关系就是child = parent * 2 + 1；右孩子下标就是左孩子下标再加1。要注意的是整个的组织是按照完全二叉树的方式来组织的，调整需要知道父亲和孩子节点的下标关系。而孩子节点的下标在整个数组有效长度里面就说明存在的，比如父节点为5下标的节点。

private void shiftDown(int root, int len) {        int parent = root;        int child = 1 + root << 1;}

然后就开始循环调整。整个堆成为大根堆，不能只调整一部分，要调整到从根节点到叶子节点的全部。大根堆是父亲节点的值大于孩子节点的。所以需要先找到孩子节点的最大值，再和父亲节点对比交换。

进入循环的条件是只要有孩子就可以调整了。父亲节点和孩子节点调整的前提是至少要有一个孩子。进入循环后，寻找左右孩子的最大值和父亲节点交换。寻找的前提是要存在左右孩子。

找到孩子的最大值后，就和父节点对比，交换。如果没有交换，说明已经是大根堆了，就直接结束循环。否则，就移动父亲节点到孩子节点的位置继续调整。

建立堆的时间复杂度是O(N)。

private void shiftDown(int root, int len) {        int parent = root;        int child = 1 + root << 1;        //进入这个循环,至少有一个孩子        while (child < len) {            //如果有右孩子,找到左右孩子的最大值            if (child + 1 < len && this.elem[child] < this.elem[child + 1]) {                ++child;            }            //child一定是最大值的下标            //进行交换            if (this.elem[child] > this.elem[parent]) {                swap(elem, parent, child);                parent = child;                child = 1 + parent << 1;            } else {                break;            }        }    }    private void swap(int[] elem, int parent, int child) {        int tmp = this.elem[child];        this.elem[child] = this.elem[parent];        this.elem[parent] = tmp;    }

堆的插入是把元素插入到堆的尾部，也就是数组的尾部，然后进行调整。插入的时候要判断数组元素的空间够不够，不够的话就进行扩容。因为要调整的是一条路径，需要向上调整。使用push方法。调整的方法使用shiftUp方法。

public void push(int val) {        //判断是不是满了        if (isFull()) {            elem = Arrays.copyOf(elem,2 * elem.length);            elem[usedSize] = val;            //开始调整            shiftUp(usedSize);            ++usedSize;        }    }

private boolean isFull() {        return usedSize == elem.length;    }

因为整个数据按照完全二叉树的形式组织的，所以，新插入的元素要找到它的父亲节点。对于孩子节点，设下标为i，它的父亲节点下标为 （ i - 1 ）/ 2。就然后进行比较交换。这里的交换可以直接使用前面的swap方法。一次比较交换完成后，还要继续比较，一直到整个路径上的元素调整好。如果没有，就结束。

private void shiftUp(int child) {        int parent = (child - 1) >>> 1;        while (child > 0) {            if (elem[child] > elem[parent]) {                int tmp = elem[child];                elem[child] = elem[parent];                elem[parent] = tmp;                child = parent;                parent = (child - 1) >>> 1;            } else {                break;            }        }    }

堆删除需要删除堆顶的元素，但是不能直接在堆顶上删，而是要把堆顶元素和堆尾元素交换后来删除。减少有效元素个数，同时，对堆顶元素进行向下调整。整个的过程需要保持大根堆。删除之前先要判断这个堆是不是空的堆。

public void poll() {        if (isEmpty()) {            return;        }        int tmp = elem[0];        elem[0] = elem[usedSize - 1];        elem[usedSize - 1] = tmp;        --usedSize;        //调整        shiftDown(0, usedSize);    }    //判断堆是不是空    private boolean isEmpty() {        return usedSize == 0;    }

从堆的插入和删除来看，堆的操作中的核心就是对堆的向上调整和向下调整方法。

5、获取堆顶元素

直接返回第一个元素下标就可以。如果是空的堆，就返回-1。

public int peek() {        if (isEmpty()) {            return -1;        }        return elem[0];    }

要从小到大排序，需要建立大根堆，而从大到小排序，需要建立小根堆。从最后一个元素开始调整。每一次调整将该元素与堆顶元素交换，在向下调整。

public void HeapSort() {        int end = this.usedSize - 1;        while (end > 0) {            swap(this.elem, 0, end);            shiftDown(0, end);            --end;        }    }

堆中最重要的几个操作都调用了向上调整方法或向下调整方法。搞明白这两个方法是关键。

7、Java官方的实现

Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列，PriorityQueue是线程不安全的，PriorityBlockingQueue是线程安全的，这里介绍PriorityQueue。

使用这个方法的时候，要注意：

（1）PriorityQueue中放置的元素必须要能够比较大小，不能插入无法比较大小的对象，否则会抛出 ClassCastException异常；

（2）不能插入null对象，否则会抛出NullPointerException；

（3）PriorityQueue默认情况下是小堆---即每次获取到的元素都是最小的元素。

PriorityQueue (Java Platform SE 7 ) (oracle.com)

PriorityQueue<Integer> queue = new PriorityQueue<Integer>();        queue.add(3);        queue.add(2);        queue.add(1);        System.out.println(queue);        System.out.println("=============");        queue.poll();        System.out.println(queue);        System.out.println("=============");        System.out.println(queue.peek());

要改为大堆创建的形式，需要实现接口。

class IntCmp implements Comparator<Integer> {    @Override    public int compare(Integer o1, Integer o2) {        return o2 - o1;    }}public class Main {    public static void main(String[] args) {        PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new IntCmp());        queue.offer(3);        queue.offer(2);        queue.offer(1);        System.out.println(queue);        System.out.println("=============");        queue.poll();        System.out.println(queue);        System.out.println("=============");        System.out.println(queue.peek());    }}