Реализация минимальной кучи с использованием приоритетной очереди

Введение

В этом практическом занятии мы научимся реализовывать минимальную кучу с использованием приоритетной очереди на C++. Мы напишем программу на C++, которая сможет выполнять базовые операции с минимальной кучей.

Skills Graph

Создайте новую программу на C++

Создайте новую программу на C++ в директории ~/project, выполнив следующие команды в терминале:

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++. Мы определили функцию для вывода элементов минимальной кучи, создали приоритетную очередь целых чисел, заполнили ее элементами и вывели количество элементов в минимальной куче, первый элемент или элемент с наивысшим приоритетом, элементы минимальной кучи, минимальную кучу после удаления наименьшего элемента и количество элементов в минимальной куче после удаления наименьшего элемента.