[k-mooc/자료구조] 09. 우선 순위 큐(Priority Queue)와 힙(Heap)

 

 

우선 순위 큐(Priority Queue)

가장 우선 순위가 높은 원소가 가장 먼저 제거되는 큐

연산과 성능

연산	설명	시간 복잡도
추가(Push)	큐에 새로운 원소를 삽입하는 연산으로, 새로운 원소의 위치는 그 중요도에 따라서 결정된다.	O(n)
제거(Pop)	큐에서 가장 우선 순위가 높은 원소(가장 앞에 있는 원소)를 삭제한다.	O(n)
탑(Top)	큐에서 가장 우선 순위가 높은 원소를 조회한다.	O(1)

 

탑의 성능은 좋지만…
추가와 제거의 성능을 향상시킬 수 있는 방법은?

 

 

힙(Heap)

이진 트리를 기반으로 구현된 우선 순위 큐 — 완전 이진 트리

• 최대 힙(Max heap): 모든 노드의 값 > 자식 노드의 값 — 큰 숫자가 우선
• 최소 힙(Min heap): 모든 노드의 값 < 자식 노드의 값 — 작은 숫자가 우선

힙은 (1)포인터나 (2)배열을 기반으로 구현할 수 있는데, 배열 구현으로 설명한다.
배열을 기반으로 힙을 구현하기 위해서는 정렬된 배열의 첫 번째 원소부터 번호를 1부터 부여한다.

 

배열로 구현한 힙에서 k번째 노드의 부모 노드나 자식 노드에 접근하는 방법:

k번째 노드의 부모 노드	k/2
k번째 노드의 왼쪽 자식 노드	2*k
k번째 노드의 오른쪽 자식 노드	2*k + 1

 

자료구조

int *heap;
int n;       //힙의 전체 크기 - 메모리 크기 할당 
int cnt;     //저장된 원소 개수 

cnt = 0;    
n = 1000;
heap = (int*)calloc(n, sizeof(int));

 

📍 heapify(k)

k번째 노드로부터 힙을 재구성하는 함수

 

1. 하향식 재구성(Topdown heapify): 리프 노드까지 힙을 재구성 ⇒ max heap

/* max-heapify: 하향식 재구성 */
void heapify_topdown(int idx) {
	//리프 노드에 도착했다면 종료(왼쪽 자식 노드 주소가 카운트(전체 노드 개수)보다 크다면 존재하지 않으므로 리프 노드 - 완전 이진 트리이므로 왼쪽부터 노드를 채우니까)
	if(2*idx > cnt) return;
	
	//왼쪽 자식 노드 주소가 카운트와 같다면 이 자식 노드가 트리의 마지막 노드 -> 오른쪽 자식 노드는 없음
	//그러니까 현재 노드와 왼쪽 자식 노드만 비교: 자식이 더 크다면 자리 교환
	if(2*idx == cnt) {
		if(heap[idx] < heap[2*idx]) swap(&heap[idx], &heap[2*idx]);
		return;
	}
	
	//오른쪽 자식 노드와 비교하고 오른쪽 자식 노드로 내려가서 다시 히피파이
	if(heap[2*idx] > heap[2*idx+1] && heap[2*idx] > heap[idx]) {
		swap(&heap[idx], &heap[2*idx]);
		heapify_topdown(2*idx);
	}

	//왼쪽 자식 노드와 비교하고 왼쪽 자식 노드로 내려가서 다시 히피파이
	else if(heap[2*idx+1] > heap[2*idx] && heap[2*idx+1] > heap[idx]) {
		swap(&heap[idx], &heap[2*idx+1]);
		heapify_topdown(2*idx+1);
	}
}

 

 

2. 상향식 재구성(Bottomup heapify): 루트 노드까지 힙을 재구성 ⇒ min heap

/* min-heapify: 상향식 재구성 */
void heapify_bottomup(int idx) {
	//상향식이므로 루트 노드에 도착하면 종료 
	if(idx == 1) return;
	
	//상향식이므로 자식 노드의 좌우 상관없이 자식노드는 부모노드와 비교하면 된다.
	if(heap[idx/2] < heap[idx]) {
		swap(&heap[idx/2], &heap[idx]);
		heapify_bottomup(idx/2);
	}
}

 

n개의 노드가 있을 때 heapify(k)의 시간 복잡도:

완전 이진 탐색 트리의 depth는 O(logn)이다. 그런데 최악의 경우 검색은 리프 노드 또는 루트 노드에서 끝나게 되므로 시간 복잡도는 O(logn)이 된다.

 

 

 

힙의 연산: 추가와 제거

추가(Push)

최대 힙에 새로운 원소를 추가한다고 가정한다. 이 때, 최대 힙은 (1)완전 이진 트리이면서 (2)항상 부모 노드의 값이 자식 노드의 값보다 커야 한다.

“힙에 새로운 원소를 추가한다”라는 말의 의미는 “새로운 노드를 생성한다”는 연산인데, (1)완전 이진 트리 조건 때문에 새롭게 생성된 노드는 항상 맨 마지막 위치(리프 노드)에만 삽입될 수 있다. 그러나 이 위치에 노드가 저장되었을 때 조건 (2)를 만족시킨다는 보장이 없기 때문에 `heapify()` 를 이용해 새로운 원소가 삽입된 힙을 재구성해야한다.

구현

void insert(int ndata) {
	//cnt 증가 + 힙 마지막 위치에 새로운 원소를 저장 O(1)
	cnt++;
	heap[cnt] = ndata;
	
	//힙 재구성 o(logn)
	heapify_bottomup(cnt);
}

힙의 추가 연산 시간 복잡도는 O(logn)이 된다.

 

 

제거(Pop)

최대 힙에서 원소를 제거한다고 가정한다. 이 때, 최대 힙은 (1)완전 이진 트리이면서 (2)항상 부모 노드의 값이 자식 노드의 값보다 커야 한다.

“힙에서 원소를 제거한다”라는 말의 의미는 “루트 노드에 저장된 값을 제거한다”는 연산인데, 조건 (1) 때문에 “제거”할 수 있는 노드는 마지막 노드(리프 노드) 뿐이다. 그렇기 때문에 힙의 마지막 노드에 저장된 값을 루트 노드로 옮기고 마지막 노드를 제거한 뒤에, 루트 노드로부터 하향식 힙 재구성을 수행해야 한다.

구현

int remove() {
	//마지막 노드의 값을 루트 노드에 옮기고, 카운트를 감소 O(1)
	int temp = heap[1];
	heap[1] = heap[cnt];
	cnt--;
	
	//루트 노드로부터 힙을 하향식 재구성 O(logn)
	heapify_topdown(1);
	return temp;
}

힙의 제거 연산 시간 복잡도는 O(logn)이 된다.