一、堆的引入
根据百度百科的介绍，堆(Heap)是计算机科学中一类特殊的数据结构，是最高效的优先级队列。堆通常是一个可以被看作一棵完全二叉树的数组对象。
1.1堆的释义
堆（heap）是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：
堆中某个结点的值总是不大于或不小于其父结点的值；
堆总是一棵完全二叉树。
将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。
若将和此次序列对应的一维数组（即以一维数组作此序列的存储结构）看成是一个完全二叉树，则堆的含义表明，完全二叉树中所有非终端结点的值均不大于（或不小于）其左、右孩子结点的值。由此，若序列{k1,k2,…,kn}是堆，则堆顶元素（或完全二叉树的根）必为序列中n个元素的最小值（或最大值）。
1.2建堆效率
n个结点的堆，高度d = logn。根为第0层，则第i层结点个数为2^i，考虑一个元素在堆中向下移动的距离，这种算法时间代价为O(N)。
由于堆有层深，插入结点、删除普通元素和删除最小元素的平均时间代价和时间复杂度都是O(logN)。
二、优先级队列的模拟实现
2.1什么是优先队列
优先队列也是一种抽象数据类型。优先队列中的每个元素都有优先级，而优先级高（或者低）的将会先出队，而优先级相同的则按照其在优先队列中的顺序依次出队。
也就是说优先队列，通常会有下面的操作：
将元素插入队列
将最大或者最小元素删除
这样的话，我们完全可以使用链表来实现，例如以O（1）复杂度插入，每次在表头插入，而以O(N)复杂度执行删除最小元素；或者以O(N)复杂度插入，保持链表有序，而以O(1)复杂度删除。
然而优先队列往往使用堆来实现，以至于通常说堆时，就自然而然地想到了优先队列。
2.2通过堆模拟实现优先级队列
2.2.1创建堆
定义堆结构，并创建一个堆
public class PriorityQueue { public int[] elem; public int size; public PriorityQueue() { this.elem = new int[10]; } public void createHeap(int[] array) { //将接收到的数组放到堆中 for (int i = 0; i < array.length; i++) { elem[i] = array[i]; size++; } for (int parent = (size - 1 - 1) / 2; parent >= 0; parent--) { shiftDown(parent, size); } } /** * * @param root 是每棵子树的根节点的下标 * @param len 是每棵子树调整结束的结束条件 * 向下调整的时间复杂度：O(logn) */ public void shiftDown(int parent, int len) { int child = parent * 2 + 1; //保证有左孩子 while (child < len) { //保证不会越界 child + 1 < len if (child + 1 < len && elem[child] < elem[child + 1]) { child = child + 1; } if (elem[child] > elem[parent]) { //交换 int tmp = elem[child]; elem[child] = elem[parent]; elem[parent] = tmp; parent = child; child = parent * 2 + 1; } } } }
2.2.2入队
/** * 入队：仍然要保持是大根堆 * 向上调整 * * @param val */ public void push(int val) { //判断是否为满 if (isFull()) { elem = Arrays.copyOf(elem, 2 * elem.length); } //存数据 elem[size] = val; size++; shiftUp(size - 1); } /** * 向上调整 * * @param child */ private void shiftUp(int child) { int parent = (child - 1) / 2; while (parent > 0) { if (elem[parent] < elem[child]) { int tmp = elem[child]; elem[child] = elem[parent]; elem[parent] = tmp; child = parent; parent = (child - 1) / 2; } else { break; } } } /** * 判断堆是否满 * * @return */ public boolean isFull() { return size == elem.length; }
2.2.3出队
/** * 出队【删除】：每次删除的都是优先级高的元素 * 仍然要保持是大根堆 * 0下标和最后一个下标交换 * 再进行向下调整 */ public void pollHeap() { if (isEmpty()) { throw new HeapEmptyException("优先级队列是空的！！！"); } int tmp = elem[0]; elem[0] = elem[size - 1]; elem[size - 1] = tmp; size--; shiftDown(0, size); } public boolean isEmpty() { return size == 0; }
2.2.4获取队顶元素
因为堆是由数组构成的，获得队顶元素就是取数组0下标位置的值。
/** * 获取堆顶元素 * * @return */ public int peekHeap() { if (isEmpty()) { return -1; } return elem[0]; }
