【数据结构】二叉堆一文详解，附demo

有时候也挺迷惑的，技术那么多，感觉学什么都来不及，又什么都得学，经常一看别人，哇，比你年轻比你厉害，然后自己emo一下又要鸡血模式，就挺无语的，但愿我们的坚持与努力都不白费吧，虽然开发可能不是一辈子的事，但但是干一天优秀一天，也是很有价值感的，加油共勉

二叉堆(Binary Heap)是一种特殊的完全二叉树数据结构，用于高效地实现优先队列。二叉堆可以分为两种类型：最小堆(Min Heap)和最大堆(Max Heap)。

在最小堆中，每个父节点的值都不大于其子节点的值；

而在最大堆中，每个父节点的值都不小于其子节点的值。

二叉堆的关键特性是它提供了对堆中元素的快速访问、插入和删除操作，所有这些操作的时间复杂度都是 O(log n)，其中 n 是堆中的元素数量。

完全二叉树与二叉堆的关系

完全二叉树是一种二叉树，除了最后一层外，每一层都是满的，并且最后一层的所有节点都尽可能地向左靠拢。二叉堆就是基于这种结构的，也就是说，二叉堆满足完全二叉树的定义，同时还要满足堆的性质。

物理存储与逻辑结构

虽然二叉堆在逻辑上表现为一棵树，但在计算机内存中通常使用数组来存储。数组的索引被用来表示树中的节点位置。具体来说有如下特性：

数组的第 0 个位置通常不使用，从第 1 个位置开始存储第一个元素（即根节点）。
对于任意节点 i：
其左子节点的位置是 2i。
其右子节点的位置是 2i + 1。
其父节点的位置是 i / 2（向下取整）。
任何索引大于或等于堆大小一半(size / 2)的节点都不可能有右孩子（因为这些节点处于树的最后一层或倒数第二层，都是叶子节点，它们最多只有一个孩子或没有孩子），这句话啥意思呢

可以看p001这个图，上图节点数是8/2=4，大于等于4的有5,6,7，8，都是叶子节点，这四个8在最底层，5,6,7在倒数第二层

这种存储方式使得二叉堆的操作非常高效，因为可以通过简单的数学运算来计算出父节点和子节点的数组位置。

基本操作

插入元素

当插入新元素时，首先将元素添加到数组的末尾，然后执行上浮操作(Bubble Up)，即比较该元素与其父节点，如果违反了堆的性质，则交换它们的位置，继续向上比较直到找到合适的位置。

删除元素

删除元素通常是删除堆顶元素（最小堆中最小的元素，最大堆中最大的元素）。首先，将堆顶元素与最后一个元素交换，然后删除原数组末尾的元素，最后执行下沉操作(Sink Down)，即比较当前堆顶元素与其子节点，如果违反了堆的性质，则与较小（最小堆）或较大（最大堆）的子节点交换位置，继续向下比较直到找到合适的位置（后面会用代码讲解，别着急）。

应用场景

二叉堆常用于实现优先队列(PriorityQueue的原理就是二叉堆)，如在任务调度、事件驱动的模拟程序、Dijkstra 算法（最短路径算法）、Huffman 编码（数据压缩）等领域。

示例代码

下面是一个简单的最小堆实现示例，使用数组存储，注释都已经写清楚了，大家可以揣摩下

java">import java.util.Arrays;
/*** 二叉堆* 最小堆在上，最大在下*/
public class MinHeap {//容量private int capacity = 10;//当前堆中元素个数private int size = 0;//堆数据private int[] data;public MinHeap(int capacity) {data = new int[capacity];this.capacity = capacity;}public static void main(String[] args) {MinHeap heap = new MinHeap(10);heap.put(4);heap.put(9);heap.put(3);heap.put(7);heap.put(2);heap.put(12);heap.put(6);heap.put(1);heap.put(5);heap.put(8);heap.print();heap.remove();heap.print();}/*** 插入节点** @param value 键值* @return 成功或失败*/public boolean put(int value) {//数组已满if (size > capacity) {System.out.println("数组已满");return false;}//直接将新节点插入到数据尾部data[size] = value;//插入节点后不满足二叉堆特性，需要重新堆化 先传后加shiftUp(size++);return true;}private void print(){System.out.println(Arrays.toString(data));System.out.println(data[0]);}/*** 自下而上堆化* @param pos 堆化的位置*/private void shiftUp(int pos) {// parent 堆化位置的父节点；计算公式：父节点=子节点*2// 向上堆化过程System.out.println("开始堆化" + pos);if (pos == 0) {return;}while (true){int parent = (pos - 1) >>> 1;System.out.println("父-" + data[parent] + " 子-" + data[pos]);if (data[parent] > data[pos]){System.out.println("交换" + parent + "和" + pos);swap(parent, pos);System.out.println("交换后-父-" + data[parent] + " 子-" + data[pos]);if (parent == 0) {break;}pos = parent;}else {break;}}}/*** 数组数据交换** @param i 下标* @param j 下标*/private void swap(int i, int j) {int tmp = data[i];data[i] = data[j];data[j] = tmp;}/*** 删除最小值 并返回该值* @return*/public int remove() {if (size < 1) {return -1;}int min = data[0];//将最后一个元素放到顶部 这个策略有可能需要堆化多次data[0] = data[--size];data[size] = 0;//重新堆化shiftDown(0);return min;}/*** 自上而下重新调整二叉堆** @param pos 开始调整位置*/private void shiftDown(int pos) {while (true) {//左子树int child = pos << 1 + 1;if (child >= size) {//没有子节点了break;}// 如果有右子树，并且右子树小于左子树，则转而考虑右子树 谁更小考虑谁，减少循环次数if (child + 1 < size && data[child + 1] < data[child]) {child++;}// 如果父节点小于任何一个子节点，则已经满足最小堆性质，退出循环if (data[pos] <= data[child]) {break;}// 否则交换父节点与较小的子节点swap(pos, child);pos = child;}}
}