数据结构-堆(二叉树的特殊)-第四天

数据结构的“堆”与内存管理的“堆”是同一个概念吗？

两者不是同一个概念，只是碰巧都叫“堆”。计算机系统内存中的堆是动态内存分配的一部分，程序在运行时可以使用它来存储数据。程序可以请求一定量的堆内存，用于存储如对象和数组等复杂结构。当这些数据不再需要时，程序需要释放这些内存，以防止内存泄漏。相较于栈内存，堆内存的管理和使用需要更谨慎，使用不当可能会导致内存泄漏和野指针等问题。
参考文献

定义

堆是一棵完全二叉树，根据成立条件可分为大顶堆和小顶堆。大（小）顶堆的堆顶元素是最大（小）的。
堆（Heap）是一种特殊的完全二叉树数据结构，通常用于实现优先队列。堆的主要特点是：
1
2

它是一种完全二叉树，除了最后一层外，每一层都是完全填充的。
最后一层的所有节点都尽可能地靠左排列。
堆中的每个节点的值与其子节点的值之间有一定的关系，这取决于堆的类型。

实现任务：

最小堆示例

#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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

输出：

Heap after insertion: 2 3 15 5 4 45 
Extracting minimum element: 2
Heap after extracting minimum: 3 4 15 5 45 
1
2
3

优先队列: 堆常用于实现优先队列，其中队列中的元素按照优先级排序。
排序算法: 堆排序是一种基于堆的比较排序算法，它可以对数组进行排序。
图算法: 如 Dijkstra 算法使用最小堆来找到图中两点之间的最短路径。
内存管理: 在计算机系统中，堆也被用来管理动态分配的内存。

总结

堆是一种高效的数据结构，通常用于实现优先队列和排序算法。