目录
开场白
顺序存储下标的关系
堆的定义
堆的实现
大顶堆
准备工作
建堆
获取最大元素
删除最大元素
删除指定索引元素
替换指定索引元素
新增元素
完整实现 & 单元测试
小顶堆
统一实现
总结
开场白
在上一篇文章中我们简要分析并实现了二叉树，本文我们将对优先级队列的另一种实现——堆进行简要分析与实现。为什么在介绍了二叉树之后才介绍堆？这是因为数据结构堆是一种特殊的完全二叉树。
顺序存储下标的关系
在多数情况下，我们通常使用二叉树的顺序存储结构来表示堆，我们需要先了解在二叉树顺序存储中是如何使用下标表示结点的父子关系的。我们先给定一个完全二叉树，二叉树结点的数据域存储此结点存储于数组中的下标。
在二叉树的顺序存储中，我们假定根节点位于数组的第 个位置。对于下标为
的结点，其双亲结点和左右子结点的下标可以通过如下方式计算。
- 如果
，则此结点是根结点，没有根结点；否则此结点的父结点下标为
；
- 左子结点的下标为
；
- 右子结点的下标为
。
我们对第一条结论给出简要证明，其余两条结论是根据二叉树的顺序存储结构特点得到的，不再赘述。
对于求解当前结点的父结点下标，不妨假设下标为 的结点的父结点下标为
，根据二叉树的顺序存储结构特点，可知下标为
的结点的左子结点下标为
，右子结点下标为
，因此如果下标为
的结点是下标为
的结点的左子结点，有
，得
，反之，如果下标为
的结点是下标为
的结点的右子结点，有
，得
，两个结果在整数除法下是等价的，因此可以认为下标为
的结点的父结点下标为
。
堆的定义
在前文我们提到，堆是优先级队列的另一种实现方案，所以我们可以将堆与优先级队列的特性比较看待，需要使用到优先级队列的场景都可以使用堆进行数据元素的维护。
堆（Heap）是一种特殊的完全二叉树，其每个结点的值都大于等于（或小于等于）其子结点的值，如果每个结点的值都大于等于其子结点的值，我们称这个堆为大顶堆（MaxHeap），反之，如果每个结点的值都小于等于其子结点的值，我们称这个堆为小顶堆（MinHeap），除了最后一层，其他层的节点都是满的，并且最后一层的节点都靠左排列。
现在给定一个元素序列 {
}
{
}，我们使用堆来维护这组数据，示意图如下。
由于堆也是一种树形数据结构，所以我们依然遵循从宏观到局部，从局部到宏观的思想来理解堆。从宏观来看，根节点的左右结点都小于等于或大于等于根节点，从局部上看，每个结点的左右子树依然满足这种规律，正是因为局部满足规则进而导致了整体满足规则。
堆的实现
大顶堆
准备工作
我们自定义名为 的类来实现相关操作，由于是基于二叉树的顺序存储结构进行操作的，所以需要定义一个数组类型的成员变量，为了方便操作，同时定义一个用于表示堆中存储元素数目的变量
。我们提供一个构造方法，传入数组参数，表示需要存储在堆中的元素序列，构造方法中需要调用自定义建堆方法
。为了方便，我重写了
方法。
public class MaxHeap {
int[] array;
int size;
public MaxHeap(int[] array) {
this.array = array;
this.size = array.length;
heapify();
}
@Override
public String toString() {
return Arrays.toString(array);
}
}建堆
需要提前指出的是，我们首先会将待维护的数组看作一个完全二叉树，然后基于此顺序存储结构的二叉树，将其改造成大顶堆。例如我们使用大顶堆维护元素序列 {
}
{
}，此时未形成堆的完全二叉树如下所示。由于使用二叉树的顺序存储结构实现堆，所以逻辑上是一个树结构，物理上是线性结构，我们认为根结点存储于数组的
位置，按照层序在数组中存储结点。
按照从局部到宏观的思路，我们需要先调整各个子树，使之成为大顶堆。我们先找到最后一个非叶子结点，即下标为 的结点
，对其进行调整。由于我们此时实现的是大顶堆，即根节点的元素值大于等于子结点的元素值，此时显然不满足，我们需要交换两个结点的位置，如下。
此时我们对于以下标为 的结点作为根的子树就调整完毕了，下来需要继续寻找倒数第二个非叶子结点，调整以此结点为根的子树，即调整以下标为
的结点为根结点的子树。由于此结点的左右子树根节点都大于此结点的元素值，我们寻找二者中的更大者与此结点进行交换，如下。
继续寻找根节点，此时来到了下标为 的结点，我们发现，此结点的左右子树根节点的元素值都大于此结点的元素值，同理，选择二者中的更大者，与此结点进行交换，如下。
此时来到了下标为 的结点，此结点的左子结点元素值大于当前结点元素值，故交换两个结点，如下。
最后来到了整棵树的根结点，根结点的左右子树根结点元素值都大于根结点元素值，我们选取二者中的更大者，将其与根结点交换，如下。
此时，我们就将一棵完全二叉树改造成了一个大顶堆。
但是上述过程没有涉及到一种特殊情况——连续交换。假设我们需要处理的堆是下图这样的结构。
此时已经处理到了整棵树的根结点，由于右子树根结点的元素值大于根结点元素值，所以需要将两个结点交换，交换完毕之后，我们发现，先前处理好的已经满足大顶堆特性的子树又需要处理，所以又要继续处理根结点的右子树。
在了解了相关操作后，我们通过代码实现建堆的操作。我们在函数 中实现相关功能，此函数中需要从最后一个非叶子结点开始，处理各个非叶子节点，根据上面的过程演示，我们不难发现对于每个结点的处理，如果当前结点小于其左右子结点，就需要将此结点与其子结点进行交换，从完全二叉树的结点深度角度来看，此结点的深度较之前更大，所以我们将这种操作形象的称为下潜。循环中每次需要调用下潜函数
，此函数需要传入各个非叶子节点在数组中的存储下标，在
函数体内通过我们先前给出的下标关系，得到其左右子树根节点的下标，然后进行判断，找到二者中更大的一个，调用自定义的交换函数
，结合我们刚才给出的连续交换（下潜）的情况，此时需要递归调用下潜函数。
private void heapify() {
for (int i = size / 2 - 1; i >= 0; i--)
down(i);
}
public void down(int parent) {
int left = parent * 2 + 1;
int right = left + 1;
int max = parent;
if (left < size && array[left] > array[max])
max = left;
if (right < size && array[right] > array[max])
max = right;
if (max != parent) {
swap(max, parent);
down(max);
}
}
public void swap(int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
获取最大元素
我们先前提到，堆实际上是优先级队列的实现方式之一，所以自然需要实现获取最值元素方法。根据大顶堆的特性，我们可以知道，堆的根结点就是整个维护的元素序列中的最大值。代码实现很容易，如下。
public int peek() {
return array[0];
}
删除最大元素
我们前文提到，大顶堆的根节点就是最大元素，难道直接利用数组删除元素的方法将索引 位置的元素覆盖吗？答案是否定的，因为索引
位置是完全二叉树的根，如果直接删除，意味着整棵树的瓦解。我们的处理方案是，先用变量接收索引
位置的元素，然后让索引
位置元素与数组存储的最后一个元素交换，此时对新的根节点执行下潜操作，然后更新
变量即可。
public int pull() {
int top = array[0];
swap(0, size - 1);
size--;
down(0);
return top;
}删除指定索引元素
其实和删除最大元素的思路是一致的，先用变量接收数组中指定索引对应的元素，然后将此元素与数组最后一个元素交换，对交换后的指定索引处的元素执行下潜操作，最后更新 变量即可。
public int pull(int index) {
int deleted = array[index];
swap(index, size - 1);
size--;
down(index);
return deleted;
}
替换指定索引元素
我们直接将新的元素存储到数组指定索引处，此时有可能会破坏堆特性，只需要对此结点进行下潜操作即可。
public void replace(int replaced) {
array[0] = replaced;
down(0);
}新增元素
对于新增操作，我们就需要引入上浮操作了。假设需要在下图所示的大顶堆中插入元素 ，我们不妨先将此元素存储到数组最后一个位置的直接后继。
此时需要根据先前给出的下标关系，找到最后一个结点的双亲结点进行存储元素值的判断，如果发现双亲结点存储的元素值小于当前结点存储的元素值，执行交换操作，此时需要继续按照相同的逻辑，判断新插入结点与其新的双亲结点存储元素的关系，直到此时已经满足堆特性或新插入的结点成为了整个堆的根节点。
public boolean offer(int offered) {
if (size == array.length)
return false;
up(offered);
size++;
return true;
}
private void up(int offered) {
int child = size;
while (child > 0) {
int parent = (child - 1) / 2;
if (offered > array[parent])
array[child] = array[parent];
else
break;
child = parent;
}
array[child] = offered;
}完整实现 & 单元测试
/**<h3>大顶堆</h3>
* @Author Arrebol
* @Date 2025/1/26 21:03
* @Project algorithm
* @Description：
*/
public class MaxHeap {
public int[] array;
public int size;
public MaxHeap(int capacity) {
this.array = new int[capacity];
}
public MaxHeap(int[] array) {
this.array = array;
this.size = array.length;
heapify();
}
public int peek() {
return array[0];
}
public int pull() {
int top = array[0];
swap(0, size - 1);
size--;
down(0);
return top;
}
public int pull(int index) {
int deleted = array[index];
swap(index, size - 1);
size--;
down(index);
return deleted;
}
public void replace(int replaced) {
array[0] = replaced;
down(0);
}
public boolean offer(int offered) {
if (size == array.length)
return false;
up(offered);
size++;
return true;
}
private void up(int offered) {
int child = size;
while (child > 0) {
int parent = (child - 1) / 2;
if (offered > array[parent])
array[child] = array[parent];
else
break;
child = parent;
}
array[child] = offered;
}
private void heapify() {
for (int i = size / 2 - 1; i >= 0; i--)
down(i);
}
public void down(int parent) {
int left = parent * 2 + 1;
int right = left + 1;
int max = parent;
if (left < size && array[left] > array[max])
max = left;
if (right < size && array[right] > array[max])
max = right;
if (max != parent) {
swap(max, parent);
down(max);
}
}
public void swap(int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
public static void main(String[] args) {
int[] array = {1, 2, 3, 4, 5, 6, 7};
System.out.println(Arrays.toString(new MaxHeap(array).array));
}
public int getSize() {
return size;
}
@Override
public String toString() {
return Arrays.toString(array);
}
}
public class MaxHeapTest {
@Test
public void testHeapify() {
int[] array = {12, 23, 8, 1, 3, 9, 27, 25, 13, 17};
MaxHeap maxHeap = new MaxHeap(array);
assertEquals(27, maxHeap.peek());
assertEquals(10, maxHeap.getSize());
}
@Test
public void testPeek() {
int[] array = {17, 8, 10, 7, 6, 13};
MaxHeap maxHeap = new MaxHeap(array);
assertEquals(17, maxHeap.peek());
}
@Test
public void testPull() {
int[] array = {17, 8, 10, 7, 6, 13};
MaxHeap maxHeap = new MaxHeap(array);
assertEquals(17, maxHeap.pull());
assertEquals(13, maxHeap.peek());
assertEquals(5, maxHeap.getSize());
}
@Test
public void testPullAtIndex() {
int[] array = {17, 8, 10, 7, 6, 13};
MaxHeap maxHeap = new MaxHeap(array);
assertEquals(13, maxHeap.pull(2));
assertEquals(17, maxHeap.peek());
assertEquals(5, maxHeap.getSize());
}
@Test
public void testReplace() {
int[] array = {17, 8, 10, 7, 6, 13};
MaxHeap maxHeap = new MaxHeap(array);
maxHeap.replace(5);
assertEquals(13, maxHeap.peek());
}
@Test
public void testOffer() {
int[] array = {17, 8, 10, 7, 6, 13};
MaxHeap maxHeap = new MaxHeap(array);
assertFalse(maxHeap.offer(20));
assertEquals(17, maxHeap.peek());
assertEquals(6, maxHeap.getSize());
}
@Test
public void testOfferOnFullHeap() {
int[] array = {17, 8, 10, 7, 6, 13};
MaxHeap maxHeap = new MaxHeap(array);
assertFalse(maxHeap.offer(20)); // Heap is full
}
@Test
public void testDown() {
int[] array = {17, 8, 10, 7, 6, 13};
MaxHeap maxHeap = new MaxHeap(array);
maxHeap.down(0);
assertEquals(17, maxHeap.peek());
}
@Test
public void testSwap() {
int[] array = {17, 8, 10, 7, 6, 13};
MaxHeap maxHeap = new MaxHeap(array);
maxHeap.swap(0, 1);
assertEquals(8, maxHeap.array[0]);
assertEquals(17, maxHeap.array[1]);
}
@Test
public void testToString() {
int[] array = {17, 8, 10, 7, 6, 13};
MaxHeap maxHeap = new MaxHeap(array);
assertEquals("[17, 8, 13, 7, 6, 10]", maxHeap.toString());
}
}小顶堆
实际上，了解了大顶堆的实现再着眼于小顶堆，就很容易了，只需要在相关位置修改判断条件即可，实现思路不再赘述，我们直接给出实现代码。
/**<h3>小顶堆</h3>
* @Author Arrebol
* @Date 2025/1/26 20:45
* @Project algorithm
* @Description：
*/
public class MinHeap {
int[] array;
int size;
public MinHeap(int capacity) {
this.array = new int[capacity];
}
public MinHeap(int[] array) {
this.array = array;
this.size = array.length;
heapify();
}
public int peek() {
return array[0];
}
public int pull() {
int top = array[0];
swap(0, size - 1);
size --;
down(0);
return top;
}
public int pull(int index) {
int deleted = array[index];
swap(index, size - 1);
size --;
down(index);
return deleted;
}
public void replace(int replaced) {
array[0] = replaced;
down(0);
}
public boolean offer(int offered) {
if (size == array.length)
return false;
up(offered);
size ++;
return true;
}
private void up(int offered) {
int child = size;
while (child > 0) {
int parent = (child - 1) / 2;
if (offered < array[parent]) {
array[child] = array[parent];
} else {
break;
}
child = parent;
}
array[child] = offered;
}
private void heapify() {
for (int i = size / 2 - 1; i >= 0; i --)
down(i);
}
public void down(int parent) {
int left = parent * 2 + 1;
int right = left + 1;
int min = parent;
if (left < size && array[left] < array[min])
min = left;
if (right < size && array[right] < array[min])
min = right;
if (min != parent) {
swap(min, parent);
down(min);
}
}
public boolean isFull() {
return size == array.length;
}
public void swap(int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
@Override
public String toString() {
return Arrays.toString(array);
}
public static void main(String[] args) {
int[] array = {12, 23, 8, 1, 3, 9, 27, 25, 13, 17};
System.out.println(Arrays.toString(new MinHeap(array).array));
}
public int getSize() {
return size;
}
}
统一实现
我们可以在类中使用一个参数来表示，当前构建的是大顶堆还是小顶堆，而没必要书写两个不同的类，我们称之为堆的统一实现，在此基础上，我们为堆增加了一个扩容机制，提高了可用性。
/**
* @Author Arrebol
* @Date 2025/1/26 21:17
* @Project algorithm
* @Description：
*/
public class Heap {
int[] array;
int size;
boolean max;
public Heap(int capacity, boolean max) {
this.array = new int[capacity];
this.max = max;
}
public int peek() {
return this.array[0];
}
public int poll() {
int top = array[0];
swap(0, size - 1);
size --;
down(0);
return top;
}
public int poll(int index) {
int deleted = array[index];
swap(index, size - 1);
size --;
down(index);
return deleted;
}
public void replace(int replaced) {
array[0] = replaced;
down(0);
}
public void offer(int offered) {
if (size == array.length)
grow();
up(offered);
size ++;
}
private void grow() {
int capacity = size + (size >> 1);
int[] newArray = new int[capacity];
System.arraycopy(array, 0, newArray, 0, size);
array = newArray;
}
private void up(int offered) {
int child = size;
while (child > 0) {
int parent = (child - 1) / 2;
boolean cmp = max ? offered > array[parent] : offered < array[parent];
if (cmp) {
array[child] = array[parent];
} else {
break;
}
child = parent;
}
array[child] = offered;
}
private void heapify() {
for (int i = size / 2 - 1; i >= 0; i --)
down(i);
}
public void down(int parent) {
int left = parent * 2 + 1;
int right = left + 1;
int maxOrMin = parent;
if (left < size && (max ? array[left] > array[maxOrMin] : array[left] < array[maxOrMin]))
maxOrMin = left;
if (right < size && (max ? array[left] > array[maxOrMin] : array[left] < array[maxOrMin]))
maxOrMin = right;
if (maxOrMin != parent) {
swap(maxOrMin, parent);
down(maxOrMin);
}
}
public boolean isFull() {
return size == array.length;
}
public void swap(int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
@Override
public String toString() {
return Arrays.toString(array);
}
public int getSize() {
return size;
}
}
总结
基于堆还可以实现堆排序，我们后面会专门出一期对常见排序算法的简要分析与实现，届时会对堆排序有所介绍。
堆的构建过程，就像人生的积累：每一步的下沉或上浮，都是为了找到属于自己的位置。
![[STM32 - 野火] - - - 固件库学习笔记 - - -十二.基本定时器](https://i-blog.csdnimg.cn/direct/0738afb79aa1416ab8a2a6f344525514.png#pic_center)
