本文主要是介绍数据结构-堆(二叉树的特殊)-第四天，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
数据结构的“堆”与内存管理的“堆”是同一个概念吗？
两者不是同一个概念，只是碰巧都叫“堆”。计算机系统内存中的堆是动态内存分配的一部分，程序在运行时可以使用它来存储数据。程序可以请求一定量的堆内存，用于存储如对象和数组等复杂结构。当这些数据不再需要时，程序需要释放这些内存，以防止内存泄漏。相较于栈内存，堆内存的管理和使用需要更谨慎，使用不当可能会导致内存泄漏和野指针等问题。
参考文献
定义
堆是一棵完全二叉树，根据成立条件可分为大顶堆和小顶堆。大（小）顶堆的堆顶元素是最大（小）的。
堆（Heap）是一种特殊的完全二叉树数据结构，通常用于实现优先队列。堆的主要特点是：
它是一种完全二叉树，除了最后一层外，每一层都是完全填充的。
最后一层的所有节点都尽可能地靠左排列。
堆中的每个节点的值与其子节点的值之间有一定的关系，这取决于堆的类型。
实现任务：
最小堆示例
#include <iostream>
#include <vector>
using namespace std;class MinHeap {
private:vector<int> heap;void heapifyUp(int i) {while (i > 0 && heap[(i - 1) / 2] > heap[i]) {swap(heap[i], heap[(i - 1) / 2]);i = (i - 1) / 2;}}void heapifyDown(int i, int n) {int smallest = i;int left = 2 * i + 1;int right = 2 * i + 2;if (left < n && heap[left] < heap[smallest]) {smallest = left;}if (right < n && heap[right] < heap[smallest]) {smallest = right;}if (smallest != i) {swap(heap[i], heap[smallest]);heapifyDown(smallest, n);}}public:MinHeap() {}void insert(int val) {heap.push_back(val);heapifyUp(heap.size() - 1);}int extractMin() {if (heap.empty()) {throw runtime_error("Heap is empty.");}int root = heap.front();heap[0] = heap.back();heap.pop_back();heapifyDown(0, heap.size());return root;}void printHeap() {for (int val : heap) {cout << val << " ";}cout << endl;}
};int main() {MinHeap minHeap;minHeap.insert(3);minHeap.insert(2);minHeap.insert(15);minHeap.insert(5);minHeap.insert(4);minHeap.insert(45);cout << "Heap after insertion: ";minHeap.printHeap();cout << "Extracting minimum element: " << minHeap.extractMin() << endl;cout << "Heap after extracting minimum: ";minHeap.printHeap();return 0;
}
输出：
Heap after insertion: 2 3 15 5 4 45
Extracting minimum element: 2
Heap after extracting minimum: 3 4 15 5 45
优先队列: 堆常用于实现优先队列，其中队列中的元素按照优先级排序。
排序算法: 堆排序是一种基于堆的比较排序算法，它可以对数组进行排序。
图算法: 如 Dijkstra 算法使用最小堆来找到图中两点之间的最短路径。
内存管理: 在计算机系统中，堆也被用来管理动态分配的内存。
总结
堆是一种高效的数据结构，通常用于实现优先队列和排序算法。
这篇关于数据结构-堆(二叉树的特殊)-第四天的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
