우선순위 큐

• 우선순위 큐(Priority Queue)란?

  • 일반적인 큐와 달리 들어온 순서와 상관없이 우선순위가 높은 데이터가 먼저 나가는 자료구조

• 특징

  • 우선순위 기반 처리: 각 요소게 우선순위 부여되어 높은 우선순위의 요소가 먼저 처리
  • 힙 구조 사용: 일반적으로 힙 구조를 사용하여 구현하기 때문에 효율적인 삽입 삭제 가능
  • 시간 복잡도: 힙을 사용하여 구현할 경우, 삽입 삭제 연산의 시간 복잡도는 O(logN)

• 구현 방식

  • 최대 힙(Max Heap): 부모 노드의 키 값이 자식 노드보다 큰 완전 이진트리
  • 최소 힙(Min Heap): 부모 노드의 키 값이 자식 노드보다 작은 완전이진트리

• 주요 연산

  • 삽입(Insert): 새로운 요소를 적절한 위치에 추가
  • 삭제(Delete): 가장 우선순위가 높은 요소를 제거
  • Peek(): 가장 우선순위가 높은 요소 반환하지만 제거는 안함

• 활용 분야

  • 게임 내 이벤트 처리: 다양한 이벤트를 우선 순위에 따라 처리
  • AI 결정 시스템: AI가 행동을 결정할 때 우선순위 큐를 사용하여 가장 중요하거나 효과적인 행동을 선택
  • 애니메이션 관리: 우선순위가 높은 애니메이션을 재생
  • 알고리즘
    • 다익스트라: 그래프의 최단 경로를 찾을 때 다음 방문할 노드를 우선순위 큐를 사용
    • A*: 출발지점부터 목표 지점까지 최단경로를 찾는데 사용

• 구현

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

using namespace std;

class priorityqueue
{
public:
    void Push(int data)
    {
        heap.push_back(data);
        PriUp(heap.size()-1);
    }

    int Pop()
    {
        int priority = heap[0];
        heap[0] = heap[heap.size()-1];
        heap.pop_back();

        if(heap.empty() == false)
            PriDown(0);

        return priority;
    }

    int Peek()
    {
        if(heap.empty() == false)
            return heap[0];
        
        return 0;
    }

    bool IsEmpty()
    {
        return heap.empty();
    }

private:
    void PriUp(int index)
    {
        while(index > 0 && heap[(index-1)/2] < heap[index])
        {
            swap(heap[(index-1)/2], heap[index]);
            index = (index-1)/2;
        }
    }

    void PriDown(int index)
    {
        int maxIndex = index;
        int left = index*2+1;
        int right = index*2+2;
    
        if(left < heap.size() && heap[left] > heap[maxIndex])
            maxIndex = left;
 
        if(right < heap.size() && heap[right] > heap[maxIndex])
            maxIndex = right;
        
        if(index != maxIndex)
        {
            swap(heap[index],heap[maxIndex]);
            PriDown(maxIndex);
        }
    }

private:
    vector<int> heap;
};

int main()
{
    priorityqueue q;

    q.Push(2);
    q.Push(3);
    q.Push(5);
    q.Push(1);
    q.Push(4);

    int a{};

    q.Pop();
    q.Pop();
    q.Pop();
    q.Pop();
}