数据结构第一弹-堆
大家好，今天和大家一起分享一下数据结构中的堆~
堆是一种特殊的树形数据结构，它通常用于实现优先队列，并且在许多算法中扮演着关键角色。今天一起探讨堆的基本概念、类型、工作原理以及实际的应用场景。
1. 堆的基本概念
堆是一种完全二叉树（Complete Binary Tree），其中每个节点的值都大于或等于（最大堆）或小于或等于（最小堆）其子节点的值。这种性质使得堆非常适合用来维护一组元素的有序性，同时保持高效的插入和删除操作。
1.1 完全二叉树
完全二叉树是一种特殊的二叉树，在这种树中，除了最后一层外，每一层都是完全填充的，并且所有结点都尽可能地向左靠拢。这意味着如果一个节点有右子节点，则它一定也有左子节点。
1.2 最大堆与最小堆
- 最大堆：父节点的值总是大于或等于任何一个子节点的值。
- 最小堆：父节点的值总是小于或等于任何一个子节点的值。
2. 堆的实现
堆可以通过数组来高效地实现。对于索引从0开始的数组，假设i是某个节点的索引，则：
- 其左子节点位于索引2*i + 1；
- 其右子节点位于索引2*i + 2；
- 其父节点位于索引(i - 1) / 2。
2.1 堆的插入操作
当向堆中插入一个新元素时，首先将其添加到数组末尾，然后通过上滤操作（Bubble Up）调整堆以恢复堆的性质。
2.2 堆的删除操作
删除操作通常涉及移除根节点（即最大或最小元素）。这时，可以将最后一个元素移动到根位置，然后通过下滤操作（Sink Down）调整堆以恢复堆的性质。
2.3 上滤操作
上滤操作是指当一个新节点被插入到堆底时，需要检查该节点是否满足堆的性质。如果不满足，则与父节点交换，直到满足为止。
2.4 下滤操作
下滤操作是指当根节点被删除后，用最后一个节点替换根节点。然后检查这个新根节点是否满足堆的性质。如果不满足，则与较大的子节点（最大堆）或较小的子节点（最小堆）交换，直到满足为止。
3. Java代码示例
下面是一个使用Java实现的最小堆的例子。我们将构建一个简单的最小堆，并提供插入、删除和打印功能。
3.1 定义最小堆类
public class MinHeap {
private int capacity; // 堆的最大容量
private int size; // 当前堆的大小
private int[] items; // 用于存储堆元素的数组
public MinHeap(int capacity) {
this.capacity = capacity;
this.size = 0;
this.items = new int[capacity];
}
// 获取父节点的索引
private int parent(int i) { return (i - 1) / 2; }
// 获取左子节点的索引
private int leftChild(int i) { return 2 * i + 1; }
// 获取右子节点的索引
private int rightChild(int i) { return 2 * i + 2; }
// 插入元素
public void insert(int item) {
if (size >= capacity) {
throw new IllegalStateException("Heap is full");
}
items[size] = item;
size++;
bubbleUp();
}
// 上滤操作
private void bubbleUp() {
int index = size - 1;
while (index > 0 && items[index] < items[parent(index)]) {
swap(index, parent(index));
index = parent(index);
}
}
// 删除最小元素
public int remove() {
if (size <= 0) {
throw new IllegalStateException("Heap is empty");
}
int root = items[0];
items[0] = items[size - 1];
size--;
sinkDown(0);
return root;
}
// 下滤操作
private void sinkDown(int k) {
int smallest = k;
int left = leftChild(k);
int right = rightChild(k);
if (left < size && items[left] < items[smallest]) {
smallest = left;
}
if (right < size && items[right] < items[smallest]) {
smallest = right;
}
if (smallest != k) {
swap(k, smallest);
sinkDown(smallest);
}
}
// 交换两个元素
private void swap(int first, int second) {
int temp = items[first];
items[first] = items[second];
items[second] = temp;
}
// 打印堆
public void printHeap() {
for (int i = 0; i < size; i++) {
System.out.print(items[i] + " ");
}
System.out.println();
}
}3.2 使用示例
public class Main {
public static void main(String[] args) {
MinHeap minHeap = new MinHeap(10);
// 插入元素
minHeap.insert(3);
minHeap.insert(2);
minHeap.insert(15);
minHeap.insert(5);
minHeap.insert(4);
minHeap.insert(45);
// 打印当前堆
minHeap.printHeap(); // 输出: 2 3 15 5 4 45
// 移除最小元素
System.out.println("Removed: " + minHeap.remove()); // 输出: Removed: 2
System.out.println("Removed: " + minHeap.remove()); // 输出: Removed: 3
// 再次打印堆
minHeap.printHeap(); // 输出: 4 5 15 45
}
}4. 堆的应用
4.1 优先队列
堆是实现优先队列的理想选择。在优先队列中，元素按照优先级进行排序，允许快速访问具有最高优先级的元素。例如，医院急诊室可能使用优先队列来管理病人，根据病情紧急程度处理病人。
4.2 排序算法
堆排序是一种基于比较的排序技术，它利用了堆的数据结构特性。该算法首先将待排序的数组构造成一个最大堆（或最小堆），然后反复移除堆顶元素并重建堆，直到所有元素都被移除。这种方法的时间复杂度为O(n log n)，并且不需要额外的空间。
4.3 图算法
在图论中，堆经常用于实现Dijkstra算法等最短路径算法。这些算法需要频繁地找到距离源点最近的未访问节点，而最小堆正好提供了这样的能力。
4.4 系统调度
操作系统中的进程调度器有时会使用堆来管理进程的优先级。这样可以确保高优先级的任务能够更快得到执行。
堆作为一种重要的数据结构，在很多领域都有着广泛的应用。通过理解堆的基本概念及其工作原理，我们可以更好地利用这一工具解决实际问题。欢迎大家一起沟通讨论~
原文地址：https://blog.csdn.net/fengxiaotao_cool/article/details/144276350
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！