우선순위 큐 Priority Queue

일반적인 Queue 같은경우 FIFO(First In First Out) 구조로

먼저 들어가 있던 데이터가 가장먼저 반환되는 자료구조이다.

 

Priority Queue는 먼저 들어가있는 순서는 상관없이

우선순위가 가장 높은것 먼저 배출되는 자료구조이다.

 

예시는 낮은수가 우선순위가 높다고 가정한다.

 

내부 원리를 이해해보자.

 

우선순위 큐는 이진트리 형식으로 구성되어있으며, 이 트리 구조를 활용해 빠르게 우선순위를 쉽게 확인할수 있다.

 

Enqueue

 

우선순위 큐에 2, 4, 3 의 데이터 3개가 들어있고 새로운 데이터 1을 삽입하는 과정

위처럼 이진트리의 순서대로 맨 마지막 자리에 전달받은 요소를 추가시켜준다.

이후 자신의 부모 노드보다 우선순위가 높다면 자리를 교체해주며 트리의 Head까지 과정을 반복해주면 된다.

 

 

Dequeue

 

이미 내부 배열의 맨 첫번째 요소는 가장 우선순위가 높은 원소로 준비되어있기때문에

arr[0] 을 추출해주면 된다.

 

그렇게되면 트리구조가 망가지게 되는데, 이때 맨 마지막 원소를 맨앞으로 가져와주며 마지막 원소는 삭제시킨다.

이후 Head의 데이터를 다시 아래쪽으로 정리(Heapify)시켜주면된다.

왼쪽 노드와, 오른쪽 노드중 우선순위가 더 높은것과 교환

 

바로 위의 과정을 반복하되, 자식노드보다 우선순위가 높거나, 더이상 탐색할 노드가 없을때까지 반복해주면 된다.

 

Dequeue 과정 정리

 

 

 

Priority Queue 구현

 

class PriorityQ
{
    int[] arr;
    int step = 1;

    public int Count{get {return step - 1;}}


    public PriorityQ()
    {
        arr = new int[3];
    }

    public void Enqueue(int element)
    {
        if(step >= arr.Length-1)
            Resize(arr.Length*2);
        // 배열의 크기가 부족할경우 기존 배열크기의 2배로 확장

        arr[step] = element;

        int idx = step;

        while (true)
        {
            if(idx <= 0)
                break;

            if(arr[idx] < arr[idx/2])
                Swap(idx,idx/2);
            else
                break; // 자신의 부모노드보가 우선순위가 낮다면 종료

            idx /= 2;
        }

        step++;
    }

    public int Dequeue()
    {
        int value = arr[1];

        arr[1] = arr[Count];
        arr[Count] = 0;
        step--;

        Heapify();

        return value;
    }

    private void Heapify()
    {
        int idx = 1;
        int priorityIdx;

        int left, right;

        while (true)
        {
            if(idx > Count-1)
                break;

            left = idx*2 > Count ? -1 : idx*2; // 저장된공간내의 요소인지 확인
            right = (idx*2)+1 > Count ? -1 : (idx*2)+1;
            priorityIdx = idx;

            if(left == -1) // 왼쪽 노드가 없다면 더이상 진행할 필요X
                break;

            if(left != -1 && arr[priorityIdx] > arr[left])
            {
                priorityIdx = left; 
            }

            if(right != -1 && arr[priorityIdx] > arr[right])
            {
                priorityIdx = right;
            }

            if(priorityIdx != idx)
                Swap(idx,priorityIdx);
            else
                break; // 교환하지 않는다면 더이상 진행할 필요X

            idx = priorityIdx; // 교환된 위치로 인덱스 이동
        }
    }

    public int Peek()
    {
        return arr[0];
    }

    private void Resize(int size)
    {
        int[] tempArr = new int[size];
        
        for (int i = 1; i < arr.Length; i++)
            tempArr[i] = arr[i];

        arr = tempArr;
    }

    private void Swap(int a, int b)
    {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}

 

미흡한 부분이나 개선될 부분이 있으면 답변 남겨주세요