详细介绍数据结构-堆

计算机中的堆数据结构

什么是堆

在计算机科学中，堆（Heap）是一种重要的数据结构，它用于在动态分配时存储和组织数据。堆是一块连续的内存区域，其中每个存储单元（通常是字节）都与另一个存储单元紧密相邻。

堆和栈是计算机内存的两种主要部分。其中，栈用于存储局部变量和函数调用的信息，而堆则用于存储动态分配的变量和数据结构。

堆的特点是可以动态地增加和减少内存，而且可以任意分配内存的大小。这意味着你可以在运行时分配内存，以存储例如动态数组，图形数据结构，优先级队列等数据。

堆的好处及适用场景

堆数据结构有许多优点，这使得它在许多计算场景中都非常有用。

1. 动态内存分配：堆允许我们在运行时动态地分配和释放内存。这意味着我们可以在程序执行的过程中，根据需要创建或删除数据。
2. 大小不定：与栈不同，堆的大小不是预先确定的。这意味着我们可以用它来存储大量的数据，只要可用的系统内存允许。
3. 支持自定义数据类型：由于堆是通用的内存分配机制，因此可以用它来存储任何类型的数据，不仅仅是基本类型。

下面是一些适用的场景：

• 动态数组：堆是创建动态数组（例如动态调整大小的数组）的理想场所。你可以在运行时根据需要增加或减少数组的大小。
• 优先级队列：优先级队列经常使用堆来实现。在这种情况下，堆的特性允许我们有效地插入和删除元素，以及在O(1)时间内查找最大（或最小）元素。
• 动态链接列表：在动态链接列表中，我们需要在运行时创建和删除节点。这也需要使用堆内存。
• 图形和树结构：图形和树结构通常使用堆来实现，因为这些数据结构需要在运行时动态地添加和删除节点。

C++代码实现一个堆并测试

以下是一个简单的最小堆的C++实现。注意这个例子只是为了教育目的，并没有包含一些关键的功能，比如防止溢出或检查是否溢出。

然后，我们可以继续实现其他堆操作，例如删除元素，查找最小元素等。以下是一个更完整的堆实现，包括上述缺失的操作：

#include   
#include   
#include   // for std::out_of_range  
  
class MinHeap {  
private:  
    std::vector<int> data;  // underlying data structure  
  
    int parent(int i) { return (i - 1) / 2; }  // parent index  
    int leftChild(int i) { return 2 * i + 1; }  // left child index  
    int rightChild(int i) { return 2 * i + 2; }  // right child index  
  
    void siftUp(int i) {  // sift element i up to its proper place  
        while (i > 0 && data[parent(i)] > data[i]) {  
            std::swap(data[parent(i)], data[i]);  
            i = parent(i);  
        }  
    }  
  
    void siftDown(int i) {  // sift element i down to its proper place  
        int minIndex = i;  // index of current minimum element  
        int l = leftChild(i);  // left child index  
        if (l < data.size() && data[l] < data[minIndex]) {  
            minIndex = l;  
        }  
        int r = rightChild(i);  // right child index  
        if (r < data.size() && data[r] < data[minIndex]) {  
            minIndex = r;  
        }  
        if (i != minIndex) {  // swap i and minIndex if necessary and repeat siftDown on affected subtree  
            std::swap(data[i], data[minIndex]);  
            siftDown(minIndex);  
        }  
    }  
  
    void siftUpForInsert(int i) {  // sift element i up to its proper place after insert for heap property to be maintained  
        while (i > 0 && data[parent(i)] > data[i]) {  
            std::swap(data[parent(i)], data[i]);  
            i = parent(i);  
        }  
    }  
  
public:  
    void insert(int value) {  // insert value into heap and maintain heap order property  
        data.push_back(value);  // append value to the end of the vector and remember its index (size - 1)  
        siftUpForInsert(data.size() - 1);  // sift up to maintain heap order property (parent is larger than its children) after insert  
    }  
  
    int extractMin() {  // extract the current minimum element from heap and maintain heap order property  
        if (data.empty()) { throw std::out_of_range("Heap is empty"); }  // heap is empty, so there is no min element throw an exception here to indicate that the situation cannot be handled and the program should stop execution with an error message to user indicating the error situation that occurred here.  
        int minElement = data[0];  // store the minimum element in a temporary variable minElement before swapping it with the last element in the vector and deleting it from the vector in the next step (data.pop_back()) as this will change the size of the vector and all further indices will shift downwards by one position in memory.  
        std::swap(data[0], data[data.size() - 1]);  // swap the first element with the last element in the vector as they will have swapped roles after this step (the last element will become the new first element/minimum element in its new position in memory while the first element will become the last element in its new position in memory after this swap operation) for maintaining the heap property after extract operation.  
        data.pop_back();  // remove the last element from the vector as it has just become unnecessary/redundant/no longer required in memory after the previous swapping step to maintain heap order property as required. As it is removed, all further indices will shift downwards by one position in memory for maintaining the heap property after extract operation.  
        siftDown(0);  // sift down the new first element/minimum element to maintain heap order property after extract operation as required. The root/first element is always at index 0 in a heap as shown in all figures above for heap data structure shown above in this code segment also. Heap is a complete binary tree (each node has either two children or no children). Binary tree is a type of tree where each node has
    }
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