欢迎 💛点赞 🌟收藏 💫关注
🏆堆
一、🎯堆的定义
堆的概念
堆是一种特殊的完全二叉树，它通过一维数组顺序存储关键码集合K={k0，k1,k2,...,kn-1}，并遵循特定的顺序关系来定义。具体来说，若对于任意节点Ki，都满足Ki <= K2i+1 且 Ki <= K2i+2（或Ki >= K2i+2），则称这样的堆为小堆。堆分为两种类型：大根堆和小根堆：
- 小根堆：根节点的值最小，父节点的值小于或等于其子节点的值；
- 大根堆：根节点的值最大，父节点的值大于或等于其子节点的值；
堆的性质
- 堆是一个完全二叉树；
- 堆中任意节点的值总是不大于（或不小于）其父节点的值；
二、🀄️堆的构建
大堆
构建过程：
代码实现：
public class Heap {
public int[] elem; // 存储元素的数组
public int usedSize; // 已使用的数组大小
public Heap() {
this.elem = new int[10];
}
// 初始化堆
public void initHeap(int[] elem) {
for (int i = 0; i < elem.length; i++) {
this.elem[i] = elem[i];
usedSize++;
}
}
// 构建大堆，通过将父节点向下调整实现
public void creatHeap() {
for (int parent = (usedSize - 1) / 2; parent >= 0; parent--) {
siftDown(parent, usedSize);
}
}
public void siftDown(int parent, int usedSize) {
int child = 2 * parent + 1;
while (child < usedSize) {
if (child + 1 < usedSize && elem[child] < elem[child + 1]) {
child++;
}
if (elem[child] > elem[parent]) {
swap(elem, child, parent);
parent = child;
child = 2 * parent + 1;
} else {
break;
}
}
}
private void swap(int[] elem, int i, int j) {
int tmp = elem[i];
elem[i] = elem[j];
elem[j] = tmp;
}
}
小堆
小堆的构建思路与大堆相似，区别在于父节点的值需要小于子节点的值。
代码实现：
```java
private void swap(int[] elem, int i, int j) {
int tmp = elem[i];
elem[i] = elem[j];
elem[j] = tmp;
}
public void creatHeap2() {
for (int parent = (usedSize - 1) / 2; parent >= 0; parent--) {
siftDown2(parent, usedSize);
}
}
public void siftDown2(int parent, int usedSize) {
int child = 2 * parent + 1;
while (child < usedSize) {
if (child + 1 < usedSize && elem[child] > elem[child + 1]) {
child++;
文章整理自互联网，只做测试使用。发布者：Lomu，转转请注明出处：https://www.it1024doc.com/4516.html
