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() 함수 정의

다음으로, Min Heap 의 요소를 출력하는 함수를 정의합니다. 이 함수는 우선순위 큐 (priority queue) 를 인수로 받으며, 원래의 우선순위 큐를 유지하기 위해 우선순위 큐의 복사본을 사용합니다.

// Function to print the elements of the Min Heap
void show(priority_queue<int, vector<int>, greater<int>> q)
{
    // Copying the Priority Queue into another to maintain the original Priority Queue
    priority_queue<int, vector<int>, greater<int>> mh = q;

    while (!mh.empty())
    {
        cout << "\t" << mh.top(); // Printing the top most element
        mh.pop();                 // Deleting the top most element to move to the next
    }

    cout << endl;
}

main() 함수 구현

main() 함수에서 정수형 우선순위 큐 (Priority Queue) 를 생성하고 요소로 채웁니다.

int main()
{
    // Creating a Priority Queue of integers
    priority_queue<int, vector<int>, greater<int>> minHeap;

    // Filling the elements into the Priority Queue
    for (int i = 1; i < 6; i++)
    {
        minHeap.push(i * 20);
    }

    // Printing the number of elements in the Min Heap
    cout << "The number of elements in the Min Heap are : " << minHeap.size() << endl;

    // Printing the first element or the element with the highest priority
    cout << "The first element or the element with the highest priority is: " << minHeap.top() << endl;

    // Printing the elements of the Min Heap
    cout << "The elements of the Min Heap are: ";
    show(minHeap);

    // Deleting the first or the smallest element from the Min Heap
    minHeap.pop();

    // Printing the Min Heap after deleting the smallest element
    cout << "After Deleting the first or the smallest element from the Min Heap, it becomes: ";
    show(minHeap);

    // Printing the number of elements in the Min Heap after deleting the smallest element
    cout << "The number of elements in the Min Heap after deleting the smallest element are : " << 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;

// Function to print the elements of the Min Heap
void show(priority_queue<int, vector<int>, greater<int>> q)
{
    // Copying the Priority Queue into another to maintain the original Priority Queue
    priority_queue<int, vector<int>, greater<int>> mh = q;

    while (!mh.empty())
    {
        cout << "\t" << mh.top(); // Printing the top most element
        mh.pop();                 // Deleting the top most element to move to the next
    }

    cout << endl;
}

int main()
{
    // Creating a Priority Queue of integers
    priority_queue<int, vector<int>, greater<int>> minHeap;

    // Filling the elements into the Priority Queue
    for (int i = 1; i < 6; i++)
    {
        minHeap.push(i * 20);
    }

    // Printing the number of elements in the Min Heap
    cout << "The number of elements in the Min Heap are : " << minHeap.size() << endl;

    // Printing the first element or the element with the highest priority
    cout << "The first element or the element with the highest priority is: " << minHeap.top() << endl;

    // Printing the elements of the Min Heap
    cout << "The elements of the Min Heap are: ";
    show(minHeap);

    // Deleting the first or the smallest element from the Min Heap
    minHeap.pop();

    // Printing the Min Heap after deleting the smallest element
    cout << "After Deleting the first or the smallest element from the Min Heap, it becomes: ";
    show(minHeap);

    // Printing the number of elements in the Min Heap after deleting the smallest element
    cout << "The number of elements in the Min Heap after deleting the smallest element are : " << minHeap.size() << endl;

    return 0;
}

요약

이 랩에서는 C++ 에서 우선순위 큐 (Priority Queue) 를 사용하여 최소 힙 (Min Heap) 을 구현하는 방법을 배웠습니다. 최소 힙의 요소를 출력하는 함수를 정의하고, 정수형 우선순위 큐를 생성하고, 요소로 채우고, 최소 힙의 요소 수, 첫 번째 요소 또는 가장 높은 우선순위의 요소, 최소 힙의 요소, 가장 작은 요소를 삭제한 후의 최소 힙, 그리고 가장 작은 요소를 삭제한 후의 최소 힙의 요소 수를 출력했습니다.

우선순위 큐를 사용한 최소 힙 구현

소개