Heap & 우선순위 큐

[psychehose]

힙 Heap

완전 이진 트리의 일종으로 두가지 조건 충족

1. 완전 이진 트리
2. 최대 힙 (부모 노드값 > 자식 노드값) , 최소 힙 (부모 노드 값 < 자식 노드값)

우선순위 큐 Priority Queue

우선순위 큐는 각 요소가 우선순위를 가지고 있으며, 우선순위가 높은 요소가 먼저 나가는 특수한 큐

1. 힙을 사용하여 효율적으로 구현 가능
2. 삽입 - 새로운 요소를 힙의 마지막에 추가한 후 힙 정렬
3. 삭제 - 힙의 루트 요소를 제거 하고 마지막 요소를 루트로 이동시킨 후 힙 정렬

• 삽입: O(log n)
• 삭제 (Olog n)
• 탐색 (루트 요소 확인): O(1)

STL을 이용한 Heap 구현

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> heap = {10, 20, 30, 5, 15};

    // 힙으로 변환
    std::make_heap(heap.begin(), heap.end());

    std::cout << "Initial max-heap: ";
    for (int i : heap) std::cout << i << " ";
    std::cout << std::endl;

    // 힙에 요소 추가
    heap.push_back(99);
    std::push_heap(heap.begin(), heap.end());

    std::cout << "After adding an element: ";
    for (int i : heap) std::cout << i << " ";
    std::cout << std::endl;

    // 힙에서 최대 요소 제거
    std::pop_heap(heap.begin(), heap.end());
    heap.pop_back();

    std::cout << "After removing the max element: ";
    for (int i : heap) std::cout << i << " ";
    std::cout << std::endl;

    return 0;
}

우선순위 큐

#include <iostream>
#include <queue>
#include <vector>

struct Task {
    int priority;
    std::string description;

    // 커스텀 비교 함수 (작은 값이 높은 우선순위)
    bool operator<(const Task& other) const {
        return priority > other.priority;
    }
};

int main() {
    std::priority_queue<Task> taskQueue;

    // 요소 삽입
    taskQueue.push({1, "Low priority task"});
    taskQueue.push({3, "High priority task"});
    taskQueue.push({2, "Medium priority task"});

    std::cout << "Tasks in priority order: ";
    while (!taskQueue.empty()) {
        Task t = taskQueue.top();
        std::cout << "(" << t.priority << ", " << t.description << ") ";
        taskQueue.pop();
    }
    std::cout << std::endl;

    return 0;
}