堆的原理与实现
责编：顶级算法 | 来源：架构师必备
概述
堆是一种数据结构，它可以保证，无论以何种顺序向堆中添加数，添加多少数，每一次取出来的都是当前堆中最小的数或者最大的数。我们可以把堆想象成一种完全二叉树结构，最小的数或最大的数在根节点的位置上，并且每一个节点都是其对应子树中的最小值或最大值。如下图所示：
一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。
但实际上我们一般使用数组来实现堆，而不是二叉树（二叉树也可以），因为任意节点的索引与它的父子节点的索引之间是有规律的。假设任意节点在数组中的索引为i，那么它的父子节点的索引与它的索引有如下关系：
父节点索引：
i/2左子节点索引：
2 * i + 1右子节点索引：
2 * i + 2
如下图所示：
如何实现堆？
插入数据
知道了堆的本质是一个数组，那么如向堆中插入数字？一般的策略是将要插入的数先放到堆的末尾，然后依次与它的的父节点的值比较，如果小于父节点的值就向上替换，直到数字不小于它的父节点的值或者已经没有父节点才停止，如下图所示：
另外，搜索公众号技术社区后台回复“算法”，获取一份惊喜礼包。
代码
// 向堆中插入元素
public void heapInsert(int num) {
// 容量不够，对数组进行扩容
if (size == array.length) {
array = enlargeArray(array);
}
array[size++] = num;
int index = size - 1;
while (index > 0) {
if (array[index] < array[index / 2]) {
swap(array, index, index / 2);
index = index / 2;
} else {
break;
}
}
}
取出最小值
取出最小值很容易实现，直接删除并返回数组中的第一个数就可以了，但为了但为了每一次取出的都是最小值，我们还应该将数组中剩下的数，也调整成一个堆的结构。一般的策略是将堆中最后一个数放到数组的第一个位置，然后和它的左右子节点中最小的值比较，如果小于子节点中的最小值，那就把它和子节点中最小的值交换，循环往复，知道不小于子节点中的值，或是已经到最后一层才停止。如下图所示：
代码
// 返回并删除最小元素
public int pop() {
int temp = array[0];
array[0] = array[--size];
int index = 0;
int left = 1;
while (left < size) {
int min = 0;
if (left + 1 < size) {
min = array[left] < array[left + 1] ? left : left + 1;
} else {
min = left;
}
if (array[index] > array[min]) {
swap(array, min, index);
index = min;
left = index * 2 + 1;
} else {
break;
}
}
return temp;
}
完整代码
每个人的具体实现不同，代码仅供参考。
public class Heap {
// 初始容量为8
private int[] array = new int[8];
private int size = 0;
public Heap() {
}
// 向堆中插入元素
public void heapInsert(int num) {
if (size == array.length) {
array = enlargeArray(array);
}
array[size++] = num;
int index = size - 1;
while (index > 0) {
if (array[index] < array[index / 2]) {
swap(array, index, index / 2);
index = index / 2;
} else {
break;
}
}
}
// 返回并删除最小元素
public int pop() {
int temp = array[0];
array[0] = array[--size];
int index = 0;
int left = 1;
while (left < size) {
int min = 0;
if (left + 1 < size) {
min = array[left] < array[left + 1] ? left : left + 1;
} else {
min = left;
}
if (array[index] > array[min]) {
swap(array, min, index);
index = min;
left = index * 2 + 1;
} else {
break;
}
}
return temp;
}
// 交换数组中两个不同索引上的值
private void swap(int[] array, int i, int j) {
array[i] = array[i] ^ array[j];
array[j] = array[j] ^ array[i];
array[i] = array[i] ^ array[j];
}
// 扩容数组
private int[] enlargeArray(int[] array) {
return Arrays.copyOf(array, array.length * 2);
}
}排序序列：
1、程序员必知必会的排序一：冒泡排序2、程序员必知必会的排序二：快速排序3、程序员必知必会的排序三：直接插入排序4、程序员必知必会的排序四：希尔排序5、程序员必知必会的排序五：拓扑排序6、程序员必知必会的排序六：选择排序7、程序员必知必会的排序七：归并排序8、程序员必知必会的排序八：基数排序9、程序员必知必会的排序九：堆排序
觉得不错？欢迎转发分享给更多人
最近有一些小伙伴，让我帮忙找一些 面试题 资料，于是我翻遍了收藏的 10T 资料后，汇总整理出来，可以说是程序员面试必备！所有资料都整理到网盘了，欢迎下载！
「顶级算法」建立了读者算法交流群，大家可以添加小编微信进行加群。欢迎有想法、乐于分享的朋友们一起交流学习。
扫描添加好友邀你进算法群，加我时注明【姓名+公司+职位】
版权申明：内容来源网络，版权归原作者所有。如有侵权烦请告知，我们会立即删除并表示歉意。谢谢。
往日分享：
一位大佬用了算法刷题宝典，进阿里了！
迷你天猫商城系统（附源码），改改就能接外包换钱！五大基本算法之分治算法
算法分析的正确姿势这些书，真tm肝……AES 加密算法的原理详解
十大经典排序算法（动图演示，看了都说好）
常见的几种加密算法比较图解：一致性协议算法动态规划之背包问题