本博文大部分为原作者知乎张晓康所写(我进行了代码的补充与完善测试)，因为写的确实很nice,还请大家多多支持原创哦。原文链接为：https://zhuanlan.zhihu.com/p/37473451
前言
本篇博客我们介绍另外一种数据结构——堆，注意这里的堆和我们Java语言，C++语言等编程语言在内存中的“堆”是不一样的，这里的堆是一种树，由它实现的优先级队列的插入和删除的时间复杂度都为O(logN)，这样尽管删除的时间变慢了，但是插入的时间快了很多，当速度非常重要，而且有很多插入操作时，可以选择用堆来实现优先级队列。
1、堆的定义
①、它是完全二叉树，除了树的最后一层节点不需要是满的，其它的每一层从左到右都是满的。注意下面两种情况，第二种最后一层从左到右中间有断隔，那么也是不完全二叉树。
②、它通常用数组来实现。
这种用数组实现的二叉树，假设节点的索引值为index，那么：
节点的左子节点是 2*index+1，
节点的右子节点是 2*index+2，
节点的父节点是 （index-1）/2。
③、堆中的每一个节点的关键字都大于（或等于）这个节点的子节点的关键字。
这里要注意堆和前面说的二叉搜索树的区别，二叉搜索树中所有节点的左子节点关键字都小于右子节点关键字，在二叉搜索树中通过一个简单的算法就可以按序遍历节点。但是在堆中，按序遍历节点是很困难的，如上图所示，堆只有沿着从根节点到叶子节点的每一条路径是降序排列的，指定节点的左边节点或者右边节点，以及上层节点或者下层节点由于不在同一条路径上，他们的关键字可能比指定节点大或者小。所以相对于二叉搜索树，堆是弱序的。
2、遍历和查找
前面我们说了，堆是弱序的，所以想要遍历堆是很困难的，基本上，堆是不支持遍历的。
对于查找，由于堆的特性，在查找的过程中，没有足够的信息来决定选择通过节点的两个子节点中的哪一个来选择走向下一层，所以也很难在堆中查找到某个关键字。
因此，堆这种组织似乎非常接近无序，不过，对于快速的移除最大（或最小）节点，也就是根节点，以及能快速插入新的节点，这两个操作就足够了。
3、移除
移除是指删除关键字最大的节点（或最小），也就是根节点。
根节点在数组中的索引总是0，即maxNode = heapArray[0];
移除根节点之后，那树就空了一个根节点，也就是数组有了一个空的数据单元，这个空单元我们必须填上。
第一种方法：将数组所有数据项都向前移动一个单元，这比较费时。
第二种方法：
①、移走根
②、把最后一个节点移动到根的位置
③、一直向下筛选这个节点，直到它在一个大于它的节点之下，小于它的节点之上为止。
具体步骤如下：
图a表示把最后一个节点移到根节点，图b、c、d表示将节点向下筛选到合适的位置，它的合适位置在最底层（有时候可能在中间），图e表示节点在正确位置的情景。
注意：向下筛选的时候，将目标节点和其子节点比较，谁大就和谁交换位置。
4、插入
插入节点也很容易，插入时，选择向上筛选，节点初始时插入到数组最后第一个空着的单元，数组容量大小增一。然后进行向上筛选的算法。
注意：向上筛选和向下不同，向上筛选只用和一个父节点进行比较，比父节点小就停止筛选了。
5、完整的Java堆代码
首先我们要知道用数组表示堆的一些要点。若数组中节点的索引为x，则：
节点的左子节点是 2*index+1，
节点的右子节点是 2*index+2，
节点的父节点是 （index-1）/2。
注意："/" 这个符号，应用于整数的算式时，它执行整除，且得到是是向下取整的值.
import java.util.LinkedList;
import java.util.Queue;
public class Heap {
public static void main(String[] args) {
Heap heap = new Heap(11);
int a[] = new int[] { 1, 8, 2, 3, 60, 50 };
for (int i = 0; i < a.length; i++) {
heap.insert(a[i]);
}
// heap.remove();
heap.change(0, 20);
heap.display();
}
int[] heapArray;
int maxSize;
int currentSize;
public Heap(int size) {
this.maxSize = size;
heapArray = new int[maxSize];
}
// 插入
public void insert(int key) {
if (isFull()) {
return;
}
heapArray[currentSize] = key;
trickleUp(currentSize++);
}
// 删除
public void remove() {
heapArray[0] = heapArray[--maxSize];
trickledown(0);
}
// 根据索引更改数据
public void change(int index, int newval) {
if (index < 0 || index > maxSize - 1) {
return;
}
int oldval = heapArray[index];
heapArray[index] = newval;
if (oldval > newval) {
trickledown(index);
} else {
trickleUp(index);
}
}
// 上移
public void trickleUp(int index) {
int parent = (index - 1) / 2;// 父节点的索引
int key = heapArray[index];
while (index > 0 && heapArray[parent] < key) {
heapArray[index] = heapArray[parent];
index = parent;
parent = (parent - 1) / 2;
}
heapArray[index] = key;
}
// 下移
public void trickledown(int index) {
int key = heapArray[index];
int max;
while ((2 * index + 2) <= maxSize) {
int lchild = 2 * index + 1;
int rchild = lchild + 1;
if (heapArray[lchild] < heapArray[rchild]) {
max = rchild;
} else {
max = lchild;
}
if (key < heapArray[max]) {
heapArray[index] = heapArray[max];
index = max;
} else {
break;
}
}
heapArray[index] = key;
}
public void display() {
Queue<Integer> queue = new LinkedList<Integer>();
queue.add(0);
int level = 1;
int lchild, rchild;
while (!queue.isEmpty()) {
int size = queue.size();
System.out.println("level" + level + ":");
level++;
for (int i = 0; i < size; i++) {
int index = queue.poll();
if (i % 2 == 0) {
System.out.print("\tchild" + ((i + 1) / 2 + 1) + ":");
}
System.out.print(" " + heapArray[index] + " ");
lchild = 2 * index + 1;
rchild = 2 * index + 2;
if (lchild < maxSize) {
queue.add(lchild);
}
if (rchild < maxSize) {
queue.add(rchild);
}
}
System.out.println();
}
}
public boolean isEmpty() {
return currentSize == 0;
}
public boolean isFull() {
return currentSize == maxSize;
}
class Node {
int data;
public void setkey(int data) {
this.data = data;
}
public int getkey() {
return data;
}
}
}
运行截图
