堆及其应用

堆是一种基于树结构的数据结构，通常用于实现优先队列。堆分为最大堆和最小堆两种类型，最大堆的每个节点的值都大于等于其子节点的值，最小堆则相反，每个节点的值都小于等于其子节点的值。

基础算法操作包括：

1. 插入元素：将新元素插入堆的末尾，然后通过上滤操作将其移到正确的位置。

2. 删除堆顶元素：将堆顶元素与堆末尾元素交换，然后将堆末尾元素删除，最后通过下滤操作将堆顶元素移到正确的位置。

3. 上滤操作：将一个新元素插入堆末尾后，将其与其父节点比较，如果大于等于父节点，则不需要操作；否则将其与父节点交换，然后继续向上比较，直到达到堆顶或者不需要交换为止。

4. 下滤操作：将堆顶元素与其子节点比较，如果小于等于子节点，则不需要操作；否则将其与子节点中较大（或较小）的那个交换，然后继续向下比较，直到达到堆底或者不需要交换为止。

5. 建堆操作：将一个无序序列转化为堆的过程，可以通过从最后一个非叶子节点开始进行下滤操作，直到堆顶。

以下是基于数组实现的最小堆，包括插入元素、删除堆顶元素、上滤操作、下滤操作和建堆操作的实现。

应用场景：

堆是一种数据结构，具有动态分配内存、动态扩容等特点，在计算机科学中有许多应用场景。以下是堆的几个应用场景：

1. 内存管理

堆常用于动态分配内存，例如在程序运行时需要创建一个动态数组，但是数组的大小在编译时是未知的，这时可以使用堆来动态分配内存。C语言中的malloc和free函数就是堆的常见应用。

2. 优先队列

堆可以用来实现优先队列，即队列中的元素按照某种优先级排序，每次取出的元素是优先级最高的。堆实现优先队列的时间复杂度为O(logn)，比其他实现方式的时间复杂度低，因此在需要高效实现优先队列的场景中，堆是一个常见的选择。

3. 排序算法

堆排序是一种高效的排序算法，它的时间复杂度为O(nlogn)，与快速排序、归并排序等常见的排序算法相当。堆排序的基本思路是将待排序的元素构建成一个二叉堆，然后每次取出堆顶的元素，将其放到已排序的序列中，再对剩余的元素重新构建堆。

4. 图算法

在图算法中，堆常用于实现Dijkstra算法和Prim算法。Dijkstra算法是一种求解单源最短路径问题的算法，它通过维护一个距离起点最短的节点集合，不断扩展该集合来求解最短路径。Prim算法是一种求解最小生成树问题的算法，它通过维护一个已经生成的树的节点集合，不断将与该集合相邻的未被访问的节点加入集合中，直到生成一棵最小生成树。

5. 操作系统

堆在操作系统中也有广泛的应用，例如进程管理中的内存分配和释放、虚拟内存管理中的页面置换等。在进程管理中，堆用于动态分配进程的堆内存，以及动态加载和卸载动态链接库。在虚拟内存管理中，堆可以用于实现页面置换算法中的优先队列，以便快速选择需要置换的页面。

```c++

#include <iostream>
#include <vector>using namespace std;class MinHeap {
private:vector<int> heap; // 存储堆的数组// 上滤操作void siftUp(int index) {while (index > 0) {int parent = (index - 1) / 2;if (heap[parent] > heap[index]) {swap(heap[parent], heap[index]);index = parent;} else {break;}}}// 下滤操作void siftDown(int index) {int size = heap.size();while (index * 2 + 1 < size) {int leftChild = index * 2 + 1;int rightChild = index * 2 + 2;int minIndex = leftChild;if (rightChild < size && heap[rightChild] < heap[leftChild]) {minIndex = rightChild;}if (heap[minIndex] < heap[index]) {swap(heap[minIndex], heap[index]);index = minIndex;} else {break;}}}public:// 插入元素void insert(int val) {heap.push_back(val);siftUp(heap.size() - 1);}// 删除堆顶元素void deleteMin() {int size = heap.size();if (size == 0) {return;}heap[0] = heap[size - 1];heap.pop_back();siftDown(0);}// 建堆操作void buildHeap(vector<int>& nums) {heap = nums;int size = heap.size();for (int i = size / 2 - 1; i >= 0; i--) {siftDown(i);}}// 获取堆顶元素int getMin() {return heap.size() == 0 ? -1 : heap[0];}// 获取堆的大小int size() {return heap.size();}// 判断堆是否为空bool empty() {return heap.empty();}
};int main() {MinHeap heap;heap.insert(3);heap.insert(2);heap.insert(1);cout << heap.getMin() << endl; // 1heap.deleteMin();cout << heap.getMin() << endl; // 2heap.insert(0);cout << heap.getMin() << endl; // 0vector<int> nums = {5, 4, 3, 2, 1};heap.buildHeap(nums);while (!heap.empty()) {cout << heap.getMin() << " ";heap.deleteMin();} // 1 2 3 4 5return 0;
}

```