Algorithm - 우선순위 큐(Priority Queue)

우선순위 큐 (Priority Queue)
일반 큐와 달리 힙(Heap) 자료구조를 가지며
우선순위가 가장 높은 자료가 먼저 꺼내지는 자료구조이다

 

우선순위 큐를 구현하는 방법 3가지

• 연결리스트와 배열
  • 시간복잡도 : 원소 추가 O(1), 검색 O(n)
  • 구현 쉬움
• 균형잡힌 이진 검색트리
  • 시간복잡도 : 원소 추가, 삭제 O(logN)
  • 구현 어려움
• 힙
  • 시간복잡도 : 원소 추가, 가장 큰 원소를 꺼내는 연산 모두 O(logN)
  • 구현 쉬움

위의 정리한 내용을 토대로 가장 효율적이며 쉬운 방법은 힙으로 구현하는 것이다.

 

힙(Heap)

추후에 상세히 다룰 예정이지만 쉽게 말하면 힙 자료구조는 '최솟값 or 최댓값을 빠르게 찾아내기 위한 완전이진트리 형태로 만들어진 자료구조'이다. 즉 기본적으로 중점을 두는 포인트는 최솟값or최댓값 빠르게 찾기이다.

 

힙의 정의

힙의 대소관계 규칙 : 부모 노드가 가진 원소는 항상 자식 노드가 가진 원소 이상이다.

이진검색트리와 달리 부모 자식 관계에만 적용되며, 왼쪽 자식과 오른쪽 자식이 갖는 원소의 크기는 제한하지 않는다.

이 규칙에 따르면 트리에서 가장 큰 원소는 트리의 루트에 들어가기 때문에 최대값을 빠르게 찾기 위한 힙의 목적에 알맞다.

또한 편향 트리가 나오지 않게 하기 위해서 힙은 트리의 높이를 항상 일정하게 유지하기 위해 트리의 구조에 제약을 둔다

 

힙은 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차있어야 하며 마지막 레벨에 노드가 있을 때는 항상 가장 왼쪽부터 채워져 있어야 한다.

 

우선순위 큐

본론으로 돌아가 우선순위 큐에 대해서 정리해보겠다.

힙과 유사한 구조를 가지고 있지만 개념은 다르다. 즉 우선순위 큐 = 힙이 아니라는 말이다.

힙 : 최솟값or최댓값 빠르게 찾아내기

우선순위 큐 : 우선순위가 높은 순서대로 요소를 제공

우리는 가장 효율적으로 힙 자료구조를 이용한 우선순위 큐를 구현하는 것이 목표이다.

 

위에 간단히 정리한 힙의 내용을 참고로 생각해보면 힙에서 모든 요소를 고려해

우선순위를 정할 필요 없이 부모 노드는 자식 노드보다 항상 우선순위가 앞선다는 조건을 만족시켜 완전이진트리 형태로 채워나가는 것

이는 곧 루트 노드는 항상 우선순위가 높은 노드라는 의미이며 최댓값or최솟값 찾기시 시간복잡도 O(1), 삽입 삭제 연산시 부모노드가 자식노드보다 우선순위만 높으면 된다(=트리의 깊이만큼만 비교를 하면 된다) 시간복잡도 O(logN)를 가져 매우 빠른 처리가 가능하다

 

부모노드와 자식노드간의 관계만 신경쓰기에 형제간 우선순위는 고려할 필요가 없으며 이러한 정렬 상태는

[반정렬 상태] or [느슨한 정렬 상태] or [약한 힙] 이라고 불리기도 한다.

 

원소를 넣을 때도 우선순위가 높은 순서대로 나올 수 있도록 유지가 되야하며 뽑을 때 또한 우선순위가 높은 순서대로 나오기만 하면 된다.

 

 

Min Heap으로 구현한 Priority Queue

package Algorithm;

public class MinPriorityQueue {

    public static class Heap{
        int[] heap = new int[n];
        int hCnt=0;

        public Heap(){}

        public void push(int x){
            heap[++hCnt] = x;
            int idx = hCnt;
            while(idx>1&&heap[idx/2]>heap[idx]){
                if(idx==1||heap[idx/2]<heap[idx]) break;
                int tmp = heap[idx/2];
                heap[idx/2]=heap[idx];
                heap[idx]=tmp;
                idx/=2;
            }

        }

        public int pop(){
            int pop = heap[1];
            heap[1] = heap[hCnt--];
            int idx = 1;
            int next;
            while(true){
                next = idx*2;
                if(next<hCnt&&heap[next]>heap[next+1]) next++;
                if(next>hCnt||heap[next]>heap[idx]) break;
                int tmp = heap[idx];
                heap[idx] = heap[next];
                heap[next] = tmp;
                idx=next;
            }
            return pop;
        }

    }

    public static int n = 100;
    public static int[] src = {9,8,5,7,1,2,3,6,4};

    public static void main(String[] args) {
        Heap heap = new Heap();
        for(int i=0;i<src.length;i++){
            heap.push(src[i]);
        }
        for(int i=0;i<src.length;i++){
            System.out.println(heap.pop()+ " ");
        }
    }
    
}

 

Max Heap으로 구현한 Priority Queue

package Algorithm;

public class MaxPriorityQueue {

    public static class Heap{
        int[] heap = new int[n];
        int hCnt=0;

        public Heap(){}

        public void push(int x){
            heap[++hCnt] = x;
            int idx = hCnt;
            while(idx>1&&heap[idx/2]<heap[idx]){
                if(idx==1||heap[idx/2]>heap[idx]) break;
                int tmp = heap[idx/2];
                heap[idx/2]=heap[idx];
                heap[idx]=tmp;
                idx/=2;
            }

        }

        public int pop(){
            int pop = heap[1];
            heap[1] = heap[hCnt--];
            int idx = 1;
            int next;
            while(true){
                next = idx*2;
                if(next<hCnt&&heap[next]<heap[next+1]) next++;
                if(next>hCnt||heap[next]<heap[idx]) break;
                int tmp = heap[idx];
                heap[idx] = heap[next];
                heap[next] = tmp;
                idx=next;
            }
            return pop;
        }

    }

    public static int n = 100;
    public static int[] src = {9,8,5,7,1,2,3,6,4};

    public static void main(String[] args) {
        Heap heap = new Heap();
        for(int i=0;i<src.length;i++){
            heap.push(src[i]);
        }
        for(int i=0;i<src.length;i++){
            System.out.println(heap.pop()+ " ");
        }
    }
    
}