[DATA STRUCTURE] 12. 우선순위 큐(Priority Queue)

우선순위 큐(Priority Queue)는 각 원소에 우선순위를 부여하고, 이 우선순위에 따라 원소들을 처리하는 자료구조다.

즉, 가장 높은 우선순위를 가진 원소가 다른 원소보다 먼저 처리된다.

그리고 이번 게시글에선 기존처럼 장단점을 나눠 정리하는 것이 아닌 구현법과 활용법을 작성할 예정이다.

 

#include <iostream>
#include <vector>

class MinHeap {
private:

    std::vector<std::pair<int, std::string>> heap;

    void heapify_up(int index) {
        
        int parent = (index - 1) / 2;

        while (index > 0 && heap[index].first < heap[parent].first) {
            
            std::swap(heap[index], heap[parent]);
            index = parent;
            parent = (index - 1) / 2;
        }
    }

    void heapify_down(int index) {

        int left_child = 2 * index + 1;
        int right_child = 2 * index + 2;
        int smallest = index;

        if (left_child < heap.size() && heap[left_child].first < heap[smallest].first) {
           
            smallest = left_child;
        }

        if (right_child < heap.size() && heap[right_child].first < heap[smallest].first) {
          
            smallest = right_child;
        }

        if (smallest != index) {
            
            std::swap(heap[index], heap[smallest]);
            heapify_down(smallest);
        }
    }

public:

    void push(std::string item, int priority) {

        heap.push_back(std::make_pair(priority, item));
        heapify_up(heap.size() - 1);
    }

    std::string pop() {

        if (heap.empty()) {

            return "Queue is empty";
        }

        std::string item = heap[0].second;
        heap[0] = heap.back();
        heap.pop_back();
        heapify_down(0);

        return item;
    }

    bool is_empty() {

        return heap.empty();
    }
};

 

 

특징

 

1. 우선순위 개념 : 각 원소는 특정한 우선순위를 가지고 있고 이 우선순위는 일반적으로 숫자로 표현되며,

낮은 숫자가 높은 우선순위를 의미할 수도 있고, 그 반대일 수도 있다.

2. 삽입 및 삭제 연산 : 주로 삽입(Insert)과 삭제(Delete) 연산을 지원하며, 삽입 시 새로운 원소가 우선순위에 맞게

적절한 위치에 삽입되고, 삭제 시에는 가장 높은 우선순위를 가진 원소가 추출된다.

3. 높은 우선순위 원소에 빠른 접근 : 주로 가장 높은 우선순위를 가진 원소에 빠르게 접근하는 데 사용된다.

이에 따라 최댓값 또는 최솟값을 빠르게 찾을 수 있다.

 

 

구현

 

1. 배열(Array) 기반 구현 : 배열을 사용하여 원소들을 저장하고, 각 원소의 우선순위에 따라 정렬된 상태를 유지하며,

삽입 및 삭제 연산 시에는 배열의 특정 위치에서 조정이 이루어진다.

2. 힙(Heap) 기반 구현 : 힙은 우선순위 큐를 구현하는 데 자주 사용되며, 최대 힙이나 최소 힙을 활용하여

가장 높은 우선순위를 가진 원소에 빠르게 접근할 수 있다.

3. 연결 리스트(Linked List) 기반 구현 : 각 원소는 다음 원소를 가리키는 링크를 가지고 있기에 삽입 및 삭제 연산 시에는

연결 리스트의 적절한 위치에서 조정이 이루어진다.

 

 

활용

 

1. 작업 스케줄링 : 다양한 작업이 있을 때, 우선순위 큐를 이용하여 가장 중요한 작업을 먼저 처리할 수 있다.

2. 알고리즘 구현 : 다익스트라 알고리즘과 같은 그래프 알고리즘에서 최소 비용이나 최단 경로를 찾는 데에 활용된다.

3. 시뮬레이션 및 이벤트 처리 : 이벤트 시뮬레이션과 같은 시스템에서 이벤트를 우선순위에 따라 처리할 때

우선순위 큐가 유용하게 사용될 수 있다.

4. 자원 관리 : 자원 할당 및 해제를 관리할 때 우선순위 큐를 이용하여 중요한 자원에 우선순위를 부여할 수 있다.