[ Collection Framework ] - 3. Priority Queue(우선순위큐)

Priority Queue?

- 우선순위 큐 : 일반적인 FIFO(First In First Out)의 Queue에서 우선순위의 개념을 도입한 Queue

- 데이터에 대한 처리 절차를 순위에 따라 처리하기 위해 사용된다!

- 보통 Heap으로 구현되어 사용된다!

언제 사용되나요?

- 많고 복잡한 데이터에 대하여 처리하는 순위를 매겨야 할 때 사용된다!

- 실제 사례

  1. 시뮬레이션 시스템

  2. 네트워크 트래픽 제어

  3. 운영체제의 작업 스케쥴링

- 삽입, 삭제의 시간복잡도가 O(logN) 이므로 순위를 매길 때, 100만번의 연산을 대략 18번의 연산으로 줄일 수 있다!!

Heap?

Heap의 구조

- 완전 이진 트리(Complete Binary Tree)의 일종으로 우선순위 큐를 위하여 만들어진 자료구조다!

cf > 완전 이진 트리 : Node의 Leaf(마지막 자식)을 제외하고, 모든 노드의 자식이 2개인 트리

- Heap은 보통 반정렬 상태를 유지한다!

cf > 반정렬 상태 : 큰 값이 상위 Depth에 있고, 작은 값이 하위 Depth에 있다!

- Heap은 배열을 이용하여 구현하게 된다!

Heap의 특성

- 인덱스에 대한 절차를 편리하게 하기 위해, 0번째 인덱스(Heap[0])는 사용하지 않는다!

- 그러면 다음과 같은 특성을 갖는다!

  1. 왼쪽 자식의 인덱스 = ( 부모 * 2 )

  2. 오른쪽 자식의 인덱스 = ( 부모 * 2 ) + 1

  3. 부모의 인덱스 = ( 자식 / 2 )

Add 절차

1. 맨 마지막 자리에 원소를 삽입한다.

2. 현재 위치에서 부모보다 우선순위가 높으면 교환한다!

3. 이러한 작업을 할 수 있을때까지 반복한다!!

- 아래 그림은 Max Heap을 기준으로 설명합니다. ( -> 원소 삽입시 (-)를 붙이면 Min Heap으로 됨! )

1. 맨 마지막 자리에 원소를 삽입한다!

2. 부모보다 우선순위가 높아서 교환!

3. 교환했더니 더 교환할 수 있다!

4. 더 이상 교환할 수 없으므로 끝!

POP 절차

1. 루트노드의 값을 제거한다.

2. 마지막 원소를 루트 노드로 가져온다!

3. 자식 노드중에서 더 큰값과 비교하여 우선순위가 자식이 더 높다면 교환한다!

4. 이러한 작업을 할 수 있을때까지 반복한다!

1. 루트노드를 제거한다!

2. 마지막 원소를 루트로 가져온다!

3. 오른쪽 자식노드가 더 크므로 교환한다!

4. 왼쪽 자식노드가 크므로 교환한다!

메서드 시간복잡도

- Add() : O(logN), 삽입시 최대 비교 연산이 N/2 만큼 진행된다.

- POP() : O(logN), 제거시 최대 비교 연산이 N/2 만큼 진행된다.

- Peek() : O(1), 루트 노드의 값을 참조한다. 

코드 구현

원본 소스

package dataStructure;
/**
 * Max Heap 구현 --> Min Heap은 삽일하고 제거할때 -기호를 붙이면 됨!!
 * Heap은 항상 [반정렬] 상태를 유지한다!!
 * => 다시 말해서, 큰 값이 depth가 깊을 수 있고, 작은 값이 depth가 작을 수 있다.
 * Heap의 왼쪽 자식 노드의 index는 left = parent * 2
 * Heap의 오른쪽 자식 노드의 index는 right = parent *2 + 1;
 * @author huisam
 * 
 * 최대 힙 문제 : https://www.acmicpc.net/problem/11279
 * 
 */
public class PriorityQueue {
    
    /** 배열의 크기를 저장할 인덱스,, 코드 구조는 보기좋게 1번째부터 시작 */
    private int length = 0;
    
    /** heap을 나타낼 배열,, 0번째 인덱스는 비운다*/
    private int []arr = new int[1000];
    
    /**
     * x와 y의 인덱스 위치의 원소를 스왑한다
     * @param x
     * @param y
     */
    private void swap(int x, int y) {
        int temp = arr[x];
        arr[x] = arr[y];
        arr[y] = temp;
    }
    
    /**
     * 힙 내부구조를 보여주기 위한 배열
     */
    public void print() {
        System.out.print("(");
        for (int i = 1; i < length; i++) {
            System.out.print(arr[i] + ", ");
        }
        System.out.println(arr[length] + ")");
    }
    
    /**
     * x인덱스의 부모 index는 자신의 값에서 /2된 값이다
     * @param x
     * @return x/2
     */
    private int parent(int x) {
        return x/2;
    }
    
    /**
     * 원소를 삽입할 때, 맨 뒤에 삽입을 한뒤
     * 부모보다 값이 높으면 해당 원소를 서로 스왑한다.
     * 이러한 작업을 할 수 있을 때까지 반복한다.
     * 시간복잡도 O(logN)
     * @param a 추가하는 값
     */
    public void add(int a) {
        arr[++length] = a;
        int i = length;
        while(i > 1 && arr[parent(i)] < arr[i]) {
            swap(parent(i), i);
            i = parent(i);
        }
    }
    
    /**
     * 1.최대 원소를 제거한다
     * 2.마지막에 있는 원소를 루트로 가져온다
     * 3.(자식노드의 값 중 최대값)보다 부모가 크면, 큰 자식노드와 교환한다 => 없으면 로직 종료
     * 4.더이상 교환이 불가능할 때까지 간다. ( i*2 까지라는 것은 왼쪽자식이 하나라도 있으면 교환을 시도한다는 것 )
     * 시간복잡도 O(logN)
     * @return Heap의 최대값, 비어있으면 -1
     */
    public int pop() {
        if(length == 0) return -1;
        
        int ret = arr[1];
        arr[1] = arr[length--];
        int i = 1;
        while(i*2 <= length) {
            int left = i*2;
            if(arr[left] < arr[left+1])
                left++;
            
            if(arr[i] >= arr[left]) break;
            swap(left, i);
            i = left;
        }
        
        return ret;
    }
    
    public static void main(String[] args) {
        PriorityQueue pq = new PriorityQueue();
        pq.add(1);
        pq.add(2);
        pq.pop();
        pq.pop();
        pq.add(3);
        pq.add(2);
        pq.add(1);
        pq.print();
        pq.pop();
        pq.print();
        pq.pop();
        pq.print();
    }
}
 

 

백준 - 최대힙 문제(11279) : https://www.acmicpc.net/problem/11279

- 라이브러리나 내 코드나 시간이 비슷해서 뿌듯(?)했다.

- 607B : 라이브러리 사용 / 1108B : 직접 구현

참고

자료구조 완전이진트리 (Complete Binary Tree)

[자료구조] 힙(heap)이란