C++ 最小堆 | 优先队列编程教程

介绍

在本实验中，我们将学习如何使用 C++ 中的优先队列（Priority Queue）实现一个最小堆（Min Heap）。我们将实现一个 C++ 程序，该程序可以对最小堆执行基本操作。

创建一个新的 C++ 程序

在终端中运行以下命令，在 ~/project 目录下创建一个新的 C++ 程序：

cd ~/project
touch main.cpp

包含必要的头文件

我们首先在程序中包含必要的头文件：

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

定义 show() 函数

接下来，我们定义一个函数来打印最小堆的元素。该函数以优先队列作为参数，并使用优先队列的副本来保持原始优先队列不变。

// 打印最小堆元素的函数
void show(priority_queue<int, vector<int>, greater<int>> q)
{
    // 将优先队列复制到另一个队列中以保持原始优先队列不变
    priority_queue<int, vector<int>, greater<int>> mh = q;

    while (!mh.empty())
    {
        cout << "\t" << mh.top(); // 打印最顶部的元素
        mh.pop();                 // 删除最顶部的元素以移动到下一个元素
    }

    cout << endl;
}

实现 main() 函数

在 main() 函数中，我们将创建一个整数类型的优先队列并填充元素。

int main()
{
    // 创建一个整数类型的优先队列
    priority_queue<int, vector<int>, greater<int>> minHeap;

    // 向优先队列中填充元素
    for (int i = 1; i < 6; i++)
    {
        minHeap.push(i * 20);
    }

    // 打印最小堆中的元素数量
    cout << "最小堆中的元素数量为：" << minHeap.size() << endl;

    // 打印第一个元素或优先级最高的元素
    cout << "第一个元素或优先级最高的元素是：" << minHeap.top() << endl;

    // 打印最小堆的元素
    cout << "最小堆的元素为：";
    show(minHeap);

    // 删除最小堆中的第一个或最小元素
    minHeap.pop();

    // 删除最小元素后打印最小堆
    cout << "删除最小堆中的第一个或最小元素后，最小堆变为：";
    show(minHeap);

    // 删除最小元素后打印最小堆中的元素数量
    cout << "删除最小元素后，最小堆中的元素数量为：" << minHeap.size() << endl;

    return 0;
}

编译并运行程序

要编译程序，请在终端中运行以下命令：

g++ main.cpp -o main

该命令会编译 main.cpp 源代码并生成一个名为 main 的可执行文件。

要运行程序，请执行以下命令：

./main

main.cpp 完整代码

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

// 打印最小堆元素的函数
void show(priority_queue<int, vector<int>, greater<int>> q)
{
    // 将优先队列复制到另一个队列中以保持原始优先队列不变
    priority_queue<int, vector<int>, greater<int>> mh = q;

    while (!mh.empty())
    {
        cout << "\t" << mh.top(); // 打印最顶部的元素
        mh.pop();                 // 删除最顶部的元素以移动到下一个元素
    }

    cout << endl;
}

int main()
{
    // 创建一个整数类型的优先队列
    priority_queue<int, vector<int>, greater<int>> minHeap;

    // 向优先队列中填充元素
    for (int i = 1; i < 6; i++)
    {
        minHeap.push(i * 20);
    }

    // 打印最小堆中的元素数量
    cout << "最小堆中的元素数量为：" << minHeap.size() << endl;

    // 打印第一个元素或优先级最高的元素
    cout << "第一个元素或优先级最高的元素是：" << minHeap.top() << endl;

    // 打印最小堆的元素
    cout << "最小堆的元素为：";
    show(minHeap);

    // 删除最小堆中的第一个或最小元素
    minHeap.pop();

    // 删除最小元素后打印最小堆
    cout << "删除最小堆中的第一个或最小元素后，最小堆变为：";
    show(minHeap);

    // 删除最小元素后打印最小堆中的元素数量
    cout << "删除最小元素后，最小堆中的元素数量为：" << minHeap.size() << endl;

    return 0;
}

总结

在本实验中，我们学习了如何使用 C++ 中的优先队列（Priority Queue）实现一个最小堆（Min Heap）。我们定义了一个函数来打印最小堆的元素，创建了一个整数类型的优先队列，填充了元素，并打印了最小堆中的元素数量、第一个元素或优先级最高的元素、最小堆的元素、删除最小元素后的最小堆以及删除最小元素后最小堆中的元素数量。

使用优先队列实现最小堆

介绍