자료구조 - 우선순위 큐

 

[우선순위 큐(Priority Queue)]

우선순위 큐는 큐와 비슷하지만, 각 요소에 우선순위가 있어서 우선순위가 높은 요소가 먼저 나가는 자료구조입니다.

 

 

우선순위 큐의 추상자료형(ADT)

객체 : n개의 element형의 우선 순위를 가진 요소들의 모임
연산 :
    create() ::= 우선순위 큐 생성
    init(q) ::= 우선순위 큐 q를 초기화
    is_empty(q) ::= 우선순위 큐 q가 비어있는지 검사
    is_full(q) ::= 우선순위 큐 q가 가득 찼는지 검사
    insert(q, x) ::= 우선순위 큐 q에 요소 x를 추가
    delete(q) ::= 우선순위 큐로부터 가장 우선순위가 높은 요소를 삭제하고 이 요소 반환
    find(q) ::= 우선순위가 가장 높은 요소 반환

 

 

 

배열을 사용한 우선순위 큐

배열을 사용하면 삽입 연산은 O(1)이지만, 삭제 연산은 O(n)입니다.

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

class PriorityQueueArray 
{
    public:
        void insert(int data)
        {
            // 데이터를 배열의 끝에 삽입
            array.push_back(data);
        }

        void deleteMax() 
        {
            if (!array.empty()) 
            {
                // 배열에서 최대값을 찾아 제거
                auto maxElement = std::max_element(array.begin(), array.end());
                array.erase(maxElement);
            }
        }

        int peekMax() 
        {
            if (!array.empty()) 
            {
                // 배열에서 최대값을 반환
                return *std::max_element(array.begin(), array.end());
            }
            throw std::runtime_error("Queue is empty");
        }

    private:
        std::vector<int> array;
};

int main()
{
    PriorityQueueArray pq;
    pq.insert(3);
    pq.insert(5);
    pq.insert(1);

    std::cout << "Max: " << pq.peekMax() << std::endl; // 5
    pq.deleteMax();
    std::cout << "Max after delete: " << pq.peekMax() << std::endl; // 3

    return 0;
}

 

 

 

 

연결 리스트를 사용한 우선순위 큐

연결 리스트를 사용하면 삽입 연산은 O(n)이지만, 삭제 연산은 O(1)입니다.

#include <iostream>
#include <list>

class PriorityQueueList 
{
    public:
        void insert(int data) 
        {
            // 올바른 위치를 찾아서 데이터 삽입
            auto it = std::lower_bound(queue.begin(), queue.end(), data);
            queue.insert(it, data);
        }

        void deleteMax() 
        {
            if (!queue.empty()) 
            {
                // 가장 앞의 요소 제거
                queue.pop_back();
            }
        }

        int peekMax()
        {
            if (!queue.empty())
            {
                // 가장 마지막 요소 반환
                return queue.back();
            }
            throw std::runtime_error("Queue is empty");
        }    

    private:
        std::list<int> queue;
};

int main() 
{
    PriorityQueueList pq;
    pq.insert(3);
    pq.insert(5);
    pq.insert(1);

    std::cout << "Max: " << pq.peekMax() << std::endl; // 5
    pq.deleteMax();
    std::cout << "Max after delete: " << pq.peekMax() << std::endl; // 3

    return 0;
}

 

 

 

 

 

 

 

 

 

 

ㅇㅅㅇ