[C++] 우선순위 큐

구현부

#include <iostream>
#include <vector>

using namespace std;

class PriorityQueue {
private:
    vector<int> heap;

    // 힙 속성 유지: 부모 노드가 자식 노드보다 크도록 만듦
    void heapifyUp(int index) {
        if (index == 0) return; // 루트 노드에 도달하면 종료

        int parent = (index - 1) / 2;
        if (heap[index] > heap[parent]) {
            swap(heap[index], heap[parent]);
            heapifyUp(parent); // 재귀적으로 부모 노드를 확인
        }
    }

    // 힙 속성 유지: 부모 노드가 자식 노드보다 크도록 만듦
    void heapifyDown(int index) {
        int leftChild = 2 * index + 1;
        int rightChild = 2 * index + 2;
        int largest = index;

        if (leftChild < heap.size() && heap[leftChild] > heap[largest]) {
            largest = leftChild;
        }
        if (rightChild < heap.size() && heap[rightChild] > heap[largest]) {
            largest = rightChild;
        }

        if (largest != index) {
            swap(heap[index], heap[largest]);
            heapifyDown(largest); // 재귀적으로 자식 노드를 확인
        }
    }

public:
    // 요소를 힙에 추가
    void push(int value) {
        heap.push_back(value); // 배열의 끝에 새 요소 추가
        heapifyUp(heap.size() - 1); // 힙 속성을 유지하기 위해 위로 올라가며 정렬
    }

    // 최댓값을 반환하고 제거
    int pop() {
        if (heap.empty()) {
            throw runtime_error("Queue is empty!");
        }

        int maxValue = heap[0]; // 최댓값 (루트)
        heap[0] = heap.back(); // 마지막 요소를 루트로 이동
        heap.pop_back(); // 마지막 요소 제거
        heapifyDown(0); // 힙 속성을 유지하기 위해 아래로 내려가며 정렬

        return maxValue;
    }

    // 최댓값을 반환하지만 제거하지 않음
    int top() const {
        if (heap.empty()) {
            throw runtime_error("Queue is empty!");
        }
        return heap[0]; // 루트 요소가 최댓값
    }

    // 큐가 비어있는지 확인
    bool empty() const {
        return heap.empty();
    }

    // 큐의 크기를 반환
    int size() const {
        return heap.size();
    }
};

int main() {
    PriorityQueue pq;

    pq.push(10);
    pq.push(15);
    pq.push(30);
    pq.push(20);
    pq.push(5);

    cout << "Max element: " << pq.top() << endl; // 30
    cout << "Popped element: " << pq.pop() << endl; // 30
    cout << "Max element after pop: " << pq.top() << endl; // 20

    return 0;
}

힙 속성

힙은 완전 이진 트리의 한 종류이며, 각 부모 노드와 자식 노드 사이에서 특정 규칙을 만족하는 구조를 가지고 있다. 이 규칙이 바로 "힙 속성"이다. 왼쪽의 그림은 최대 힙 구조로, 최상위 노드가 하위 두 자식노드보다 큰 값을 가지도록 하는 규칙을 가지고 있다. 우선순위 큐 역시 이 원리를 통해 작동하며, 따라서 pop을 해도 완전 이진 트리의 형태를 유지하기 위해 재정렬할 필요가 있다. 

 

느낀 점

자료구조 수업을 할 때 우선순위 큐는 가볍게 넘어간 감이 있어 복습 구현을 해보았다.