【数据结构与算法】二叉堆的 4 种操作

《数据结构实验指导 - C++语言版》题目集 算法6-1~4 二叉堆的 4 种操作

请编写程序，将 n 个已经满足最小堆顺序约束的数据直接读入最小堆；随后将下一个读入的数据 x 插入堆；再执行删顶操作并输出删顶的元素；最后顺次输出堆中剩余元素以检验操作的正确性。

输入格式：

输入首先给出一个正整数 c（≤1000），为最小堆的最大容量；下一行给出正整数 n（<c）；随后一行按层序遍历的顺序给出 n 个最小堆元素；最后一行给出将要插入堆的元素 x。所有堆元素均为 int 型范围内的整数。

输出格式：

在一行中输出插入后再删顶的元素，格式为 min = y，其中 y 为删顶元素值。
随后 n 行，按层序遍历的顺序每行输出一个最小堆元素。

输入样例：

10
6
1 5 3 7 9 8
2

输出样例：

min = 1
2
5
3
7
9
8

#include <iostream>
#include <vector>
using namespace std;

// 最小堆类实现
class MinHeap {
private:
    vector<int> heap;  // 存储堆元素的向量，采用1-based索引（下标从1开始）
    int capacity;      // 堆的最大容量
    int size;          // 当前堆中元素的数量

    // 向上调整：当插入新元素时，将其向上移动到正确位置以维持堆特性
    void percolateUp(int pos) {
        int x = heap[pos];  // 保存当前位置的元素值
        // 当不是根节点且父节点值大于当前元素值时，继续向上调整
        while (pos > 1 && heap[pos / 2] > x) {
            heap[pos] = heap[pos / 2];  // 将父节点值下移
            pos /= 2;                   // 移动到父节点位置
        }
        heap[pos] = x;  // 将元素放到正确位置
    }

    // 向下调整：当删除根节点后，将新的根节点向下移动到正确位置以维持堆特性
    void percolateDown(int pos) {
        int x = heap[pos];  // 保存当前位置的元素值
        int parent = pos;   // 记录当前父节点位置
        // 当存在左子节点时，继续向下调整
        while (parent * 2 <= size) {
            int child = parent * 2;  // 左子节点位置
            // 如果右子节点存在且值小于左子节点，选择右子节点
            if (child + 1 <= size && heap[child + 1] < heap[child]) {
                child++;
            }
            // 如果子节点值小于当前元素值，将子节点值上移
            if (heap[child] < x) {
                heap[parent] = heap[child];
                parent = child;  // 移动到子节点位置
            } else {
                break;  // 满足堆特性，退出循环
            }
        }
        heap[parent] = x;  // 将元素放到正确位置
    }

public:
    // 构造函数：初始化堆的容量，设置当前大小为0
    MinHeap(int c) : capacity(c), size(0) {
        heap.resize(c + 1);  // 预留c+1个空间（因为从1开始索引）
    }

    // 构建堆：从已有数据初始化堆
    void build(int n, const vector<int>& data) {
        size = n;  // 设置当前堆大小
        // 将数据复制到堆中（1-based索引）
        for (int i = 1; i <= n; i++) {
            heap[i] = data[i - 1];
        }
        // 从最后一个非叶子节点开始向下调整，构建最小堆
        for (int i = size / 2; i >= 1; i--) {
            percolateDown(i);
        }
    }

    // 插入元素：将新元素添加到堆中并维持堆特性
    void insert(int x) {
        heap[++size] = x;  // 将元素添加到堆的末尾
        percolateUp(size); // 向上调整以维持堆特性
    }

    // 删除并返回最小元素（根节点）
    int deleteMin() {
        int minVal = heap[1];          // 保存根节点值（最小值）
        heap[1] = heap[size--];        // 将最后一个元素移到根节点位置，并减小堆大小
        percolateDown(1);              // 向下调整以维持堆特性
        return minVal;                 // 返回最小值
    }

    // 打印堆中所有元素
    void print() {
        for (int i = 1; i <= size; i++) {
            cout << heap[i] << "\n";
        }
    }
};

int main() {
    int c, n;
    cin >> c >> n;              // 读取堆容量和初始数据数量
    vector<int> data(n);
    for (int i = 0; i < n; i++) {
        cin >> data[i];         // 读取初始数据
    }
    int x; 
    cin >> x;                   // 读取要插入的元素

    MinHeap h(c);               // 创建容量为c的最小堆
    h.build(n, data);           // 用初始数据构建堆

    h.insert(x);                // 插入新元素
    int minVal = h.deleteMin(); // 删除并获取最小值
    cout << "min = " << minVal << "\n";  // 输出最小值
    h.print();                  // 打印剩余元素

    return 0;
}