Priority Queue & Heap

Priority Queue

구조적으로 Queue와 유사하지만 우선순위가 높은 아이템이 먼저 처리됨

Priority Queue는 ADT (추상적인 개념)

그럼 이름을 왜 Queue라 지었는가?

Queue의 동작은 FIFO를 따름
기존 Queue는 시간적 순서에 처리하지만 이걸 Priority Queue에서는 우선순위(Priority)로 처리. 즉, 구조는 Queue와 비슷하지만 기준이 다를 뿐
엄연히 다른 자료구조이다

Heap

이진트리 구조로 구현

Priority Queue의 구현체 중 하나이다
Heap에는 Max Heap과 Min Heap이 있다 (Root에 최댓값/최솟값을 가짐)
개념적으로는 Heap은 이진 트리로 구조화 되어 있다
실제로 트리로 구현 가능하지만 주로 효율을 위해 배열/동적배열로 구현 한다

Implementation

#include<iostream>
#include<vector>
using namespace std;

class MaxHeap {
private:
    vector<int> heap;

    void heapifyUp(int index) {
        int parent = (index - 1) / 2;
        while(index > 0 && heap[index] > heap[parent]) {
            swap(heap[index] , heap[parent]);
            index = parent;
            parent = (index - 1) / 2;
        }
    }

    void heapifyDown(int index) {
        int size = heap.size();
        int large = index;
        int left = (index * 2) + 1;
        int right = (index * 2) + 2;

        if(left < size && heap[left] > heap[large]) {
            large = left;
        }
        if(right < size && heap[right] > heap[large]) {
            large = right;
        }
        if(large != index) {
            swap(heap[index], heap[large]);
            heapifyDown(large);
        }
    }

public:
    void insert(int value) {
        heap.push_back(value);
        heapifyUp(heap.size() - 1);
    }

    int deleteMax() {
        if(heap.empty()) {
            throw runtime_error("Heap is empty");
        }
        int maxVal = heap[0];
        heap[0] = heap.back();
        heap.pop_back();
        if(!heap.empty()) {
            heapifyDown(0);
        }
        return maxVal;
    }

    int peek() const {
        if(heap.empty()) {
            throw runtime_error("Heap is empty");
        }
        return heap[0];
    }

    void printHeap() const {
        for(int val : heap) {
            cout<<val<<" ";
        }
        cout<<endl;
    }
};

int main() {
    MaxHeap maxheap;

    maxheap.insert(10);
    maxheap.insert(50);
    maxheap.insert(40);
    maxheap.insert(60);
    maxheap.insert(1);

    cout<<"Heap Elements:"<<endl;
    maxheap.printHeap();

    cout<<"Max element: "<<maxheap.peek()<<endl;
    maxheap.deleteMax();
    cout<<"After Deletion"<<endl;
    maxheap.printHeap();

    return EXIT_SUCCESS;
}

Result

Complexity

연산	Time Complexity
Insert	O(log n)
Delete	O(log n)
Search	O(1)
Heap Sort	O(n log n)

Summary

우선순위 처리가 필요할 경우 효율적
최댓값/최솟값만 조회할 경우 효율적
데이터의 크기가 크고, 삽입과 삭제가 빈번한 경우 효율적

데이터의 전체 정렬이 필요할 경우 비효율적
범위 탐색 또는 특정 값 검색이 많이 요구될 때 비효율적 (BST, Hash Table, Sort 고려)

STL

std::priority_queue

우선순위 큐의 STL 구현
내부적으로 Heap(기본적으로 Max Heap)을 사용하여 동작
Min Heap으로 커스텀 가능

std::make_heap, std::push_heap, std::pop_heap

힙 알고리즘을 세부적으로 제어하거나 임의의 데이터 범위를 힙처럼 다룰 때 적합