[자료구조] 우선순위 큐(Priority Queue), 그리고 힙(Heap)

 

우선순위 큐(Priority Queue)

: 가장 높은 우선순위를 가진 항목에 접근과 삭제, 임의의 우선순위를 가진 항목 삽입을 지원하는 자료구조이다.

 

큐(Queue)라고 함은 먼저 들어오는 데이터가 먼저 나가는 자료구조인데,

앞에 우선순위가 붙어서 먼저 들어오는 데이터가 아닌 우선순위가 높은 데이터가 먼저나가는 구조인것이다.

 

힙(Heap)이란 우선순위 큐를 위해서 고안된 완전이진트리 형태의 자료구조이다.

또한 부모의 우선순위가 자식의 우선순위 보다 크다는 특징을 가지고 있어 우선 순위 큐를 구현하는데 힙을 주로 사용한다.

 

 

 

 

 

힙의 종류는 두가지가 있다.

 

• 최소 힙(Minimum Heap) : 키가 작을수록 높은 우선순위

Key(부모노드) < Key(자식 노드)

• 최대 힙(Maximum Heap) : 키가 클 수록 더 높은 우선순위

Key(부모노드) > Key(자식 노드)

 

 

힙은 완전이진트리의 형태라고 했다.

 

구조를 한번 짚어보자.

 

 

• a[i]의 자식
  • a[2xi]와 a[2xi + 1]
• a[j]의 부모
  • a[j/2] 단, j>1이고, j/2의 정수만

 

 

 

 

 

 

최소 힙 - 최솟값 접근

• 최소 힙의 루트에는 항상 가장 작은(min) 키가 있다.
  • 부모에 저장된 키가 자식의 키보다 작다는 규칙 때문이다.
  • 루트는 a[1]에 있으므로, O(1) 시간에 min 키를 가진 노드에 접근할 수 있다.

 

 

 

 

 

 

최소 힙 - 최솟값 삭제

 

루트의 키를 삭제한다.

그러면 루트에 노드가 비게되는데.. 그래서 새로운 노드를 할당시켜야 한다.

 

삭제 과정은 다음 세가지 순서를 따른다.

 

 

1. 힙의 가장 마지막 노드, 즉 배열의 가장 마지막 항목을 루트로 이동시킨다.

이렇게 해야 부모 자식 관계가 꼬이지 않아서 그런듯 하다.

 

 

2. 힙 크기를 1 감소시킨다.

 

3. 루트로부터 자식 중에서 작은 값을 가진 자식과 키를 비교하여 힙 속성이 만족될 때까지 키를 교환하며 이파리 방향으로 진행한다.

 

즉, 비교하였을 때 작은 값이 승자가 되므로 작은 값을 위로 올려보내주어야 한다.

 

 

 

세 번째 과정인 서로 비교하며 작은 값을 제일 위로 올려주는 것을 downheap()이라고 한다.

 

 

downheap에 대한 함수를 자바로 살펴보자.

 

private void downheap(int i) {
	while(2*i <= N) {
    
    	// k는 i의 왼쪽 자식이다.
    	int k = 2*i;
        
        // 만약 왼쪽 자식의 값이 오른쪽 보다 크다면 i의 오른쪽 자식 값으로 k를 바꾸어 준다.
        // 즉, i의 자식 둘 중 작은 놈을 선별하는 것
        if (k < N && a[k] > a[k+1]) k++;
        
        // 부모 노드의 값이 자식 보다 작다면 최소 힙의 조건을 만족
        // 종료
        if ( a[i] <= a[k] ) break;
        
        // 그게 아니라면 자식과 부모를 바꾸어 준다.
        swap(i, k);
        // 그리고 자식을 부모로 초기화
        i = k;
    }
}

 

그림과 함께 코드를 천천히 살펴보기를 바란다.

 

위 코드를 통해 최소값을 삭제하는 메서드 deleteMin 메서드를 작성할 수 있다.

 

public Entry deleteMin() {
	// min 값을 초기화
	Entry min = a[1];
    // 배열 맨 마지막 값과 최소 값을 교환
    swap(1, N--);
    
    // 삭제는 실제로 맨 마지막 배열 값에서 이루어짐
    a[N+1] = null;
    
    // downheap메서드를 1번째 인덱스로부터 시작;
    downheap(1);
    
    // min값 리턴
    return min;
}

 

 

 

 

 

 

최소힙 - 삽입 연산(insert)

 

 

 

 

삽입 연산은 두가지 과정을 따른다.

 

1. 힙의 마지막 노드(즉, 배열의 마지막 항목)의 바로 다음 empty 원소에 새로운 항목을 저장한다.

 

2. 루트 방향으로 올라가면서 부모의 키와 비교하여 힙 속성이 만족될 때까지 노드를 교환한다.

 

 

2번의 과정이 기존에 삭제 연산 시 downheap과 다르게 이파리로부터 올라가며 진행되기에 upheap이라고 부른다.

 

 

 

delete보단 쉽다. 삽입 연산의 메서드도 한번 살펴보자.

 

 

private void upheap(int j) {
	// j가 1보다 크다는 것은 루트 노드가 아니라는 것
    // j/2는 j의 부모를 뜻한다.
    // 즉, 부모가 자식보다 큰 경우를 뜻한다.(이 경우 swap 필요)
	while(j > 1 && a[j/2] > a[j]) {
    	// 부모와 자식 swap
    	swap(j/2, j);
        // 자식을 부모로 초기화
        j = j/2;
    }
}

 

 

upheap메서드를 통해 insert 메서드를 구현하면 다음과 같다.

 

a[++N] = temp;
upheap(N);

 

단순히 배열 크기를 하나늘려 저장해주고, upheap을 호출하기만 하면 간단하게 삽입을 할 수 있다.

 

 

 

최대 힙은 여기서 부등호만 고치면 금방 완성할 수 있다.

 

 

 

 

 

 

상향식 힙이란

 

 

 

지금까지 우리는 만들어진 힙에 대해서 삽입하고 삭제하는 과정을 살펴보았다.

 

그렇다면 힙은 어떤 방식으로 생성되는 지 알아볼 필요가 있다.

 

이는 크게 2가지 방법으로 나뉜다. 첫 번째는 삽입식 방식, 두 번째는 상향식 방식이다.

 

삽입식 방식은 키가 미리 주어져 있든, 하나씩 주어지든 상관 없이 생성이 가능하나,

상향식 방식은 미리 키가 주어져 있어야 한다.(즉, 미리 키 배열이 있어야 한다.)

 

아무튼, 두 방식 모두 랜덤으로 섞여져 있는 키 배열이 있다는 것이다.

 

 

• 상향식 방식으로 각 노드에 대해 힙 속성을 만족하도록 부모와 자식을 서로 교환한다.
• n개의 항목이 배열에 임의의 순서로 저장되어 있을 때, 힙을 만들기 위해선, a[n/2]부터 a[1]까지 차례로 downheap을 각각 수행하여 힙 속성을 충족시킨다.

 

 

위 그림은 상향식 힙을 만드는 순서이다.

 

 

상향식 힙을 만들기 위해서는 downheap을 여러차례 시행해야 한다고 했다. 코드로 한번 살펴보자.

 

public void createHeap() {
	for(int i= N/2; i>0; i--) {
    	downheap(i);
    }
}

 

 

 

 

수행 시간 분석

 

상향식 힙 생성의 수행시간은 downheap에 대한 수행 시간과 각 층마다의 노드의 수를 계산하면된다. : O(n)시간 소요

 

---

 

Insert 연산을 위한 upheap은 삽입된 노드나 키 값이 감소된 노드로 부터 최대 루트까지 올라가며 부모와 자식 노드를 교환한다.

 

delete_min 연산에서는 힙의 마지막 노드를 루트로 이동한 후, downheap을 최상위 층의 노드까지 교환해야 하는 경우가 발생한다.

 

 

즉, 두 경우 모두 층에 따라서 수행시간이 결정된다는 것이다.

 

그렇기에 수행 시간은 힙의 높이에 비례한다.

 

힙은 완전 이진 트리이므로 힙에 n개의 노드가 있으면 그 높이는 log(n+1) (이때, 소수는 올림)이다.

 

즉, 힙에 높이에 비례하는 힙의 각 연산 수행 시간은 O(logn)이다

 

 

---

References

https://slidesplayer.org/slide/17163067/

https://suyeon96.tistory.com/31