[자료구조 복습7] 우선순위 큐 - Heap 구현하기 / Heap Sort

'우선순위 큐'란 ? 우선순위큐는, 큐에 우선순위가 있는 것으로, 무작정 맨 앞의 값을 pop하는 것이 아니라, 가장 높은 우선순위의 값을 pop해주는 큐를 말한다.

 

이러한 우선순위 큐를 구현하는 가장 좋은 방법은 바로 'Heap'이다. 

일반 배열이나, 연결리스트를 사용 할 수 있겠지만, 일반 배열/ 연결리스트를 사용할 경우, 값을 올바른 위치에 넣는 시간 혹은 정렬 시키는 시간이 O(n)이므로, 비효율적이다.

반면 heap는 O(log2N)의 시간 효율을 가지므로, 다른 방법보다 유리하다.

왜 heap가 O(log2N)의 시간효율을 갖는지 알기 위해서는 heap의 구현법을 알아보자.

heap는 배열을 이용한 완전이진트리로 구현하게 된다. 완전 이진트리의 높이는 요소가 n개일 때 log2N이 된다.

heap에서 삽입시 맨 아래 요소부터 비교하면서 최악의 경우 맨 위 루트까지 비교하게 된다. 여기서 트리의 최대 높이가 log2N이므로, 삽입 최대시간은 log2N이다. 

삭제시에도 마찬가지로, 최악의 경우 맨 위부터 맨 아래까지 비교하므로 삭제의 최대시간 역시 log2N이다.

 

편의를 위해 maxHeap 구현만 보도록 하자.

 

먼저, 배열로 트리를 구현하게 되면, 부모노드의 인덱스가 i라고 했을 때 

자식노드의 인덱스는 i*2(오른쪽) 와 i*2+1 (왼쪽) 이된다.

그리고 자식노드가 j라고 했을 때, 부모노드의 인덱스는 j/2 이된다.

이를 이용하여 삽입 및 삭제 연산을 진행하면 된다. 

 

1) 구현

class element {
public:
	int key;
};
//max heap
class maxHeapType {
	element heap[MAX_ELEMENT];
	int heap_size;
public:
	maxHeapType() { heap_size = 0; };
}

일단 이렇게 heap 요소의 내용이 될 element 클래스와 heap트리 , heap_size를 멤버변수로 하고 그 외 연산을 멤버함수로 하는 클래스를 선언한다.

 

2)삽입

 

삽입 연산의 과정은 이러하다.

1) 일단 입력받은 새로운 노드를 맨 끝 노드에 집어넣는다고 생각하자. 여기서 기본 자식노드는 맨 끝노드의 인덱스이다.

2) 새로운노드 값과, 현재 자식노드와 부모노드와 비교하며, 부모노드보다 큰 경우 부모노드를 자식 노드의 자리로 옮겨준다.

3) 이렇게 계속 부모노드가 자식보다 클 때까지 반복한다.  

void insert(int num) {
	element add;
	add.key = num;
	int i = ++heap_size; //맨끝노드, heap_size 증가
	while (i!=1&&add.key > heap[i / 2].key) { //i가 root이면 i/2이 없으므로 끝
                                              //새로운 노드가 부모노드 보다 클 동안..
		heap[i] = heap[i / 2]; //부모노드를 자식노드 자리로 옮겨준다
		i = i / 2; //자식노드를 변경 -> 위에 값을 봐야하므로 
	}
	heap[i] = add; // add.key < heap[i/2].key 이거나, i가 루트 이므로 heap[i]에 add를 넣어주면 된다.
}

 

3) 삭제

 

1) 가장 크거나 작은 노드는 루트에 있으므로, 반환 할 루트 값을 복사해놓는다.

- parent 노드를 root 노드 인덱스로 지정하고, child노드를 root *2 로 지정해놓는다.

 

2) 맨 마지막 노드와 child노드를 비교해서, child노드가 더 크다면, child노드를 parent노드 자리로 놓는다.

 여기서 주의 할 점은, child노드 두개 (왼쪽, 오른쪽 ) 중에 더 큰 값을 parent노드 자리로 옮겨야한다는 것이다.

 따라서 두 child노드의 비교 역시필요하다.

 

3) 만약 맨마지막 노드 >child노드 라면, 현재 parent노드에 맨 마지막 노드가 들어가야하므로 루프를 중단한다.

 

4) parent노드에 맨 마지막 노드를 삽입한다.

 

element& remove() {
		element max = heap[1]; //root node
		element last = heap[heap_size]; //말단노드를 루트노드로 옮긴다고 생각하면 편하다.
		int parent = 1; 
		int child = 2;
		while (parent <= heap_size) { //heap[parent]에 마지막 노드를 넣어야하므로
			if (child < heap_size && heap[child + 1].key > heap[child].key)
            //child+1 <=heap_size여야 연산 수행가능!!
            //만약 왼쪽 노드가 오른쪽 노드보다 크다면
				child++; //왼쪽노드로 변경

			if (last.key >= heap[child].key) { break; } //마지막노드가 child 보다 크다면 끝
			heap[parent] = heap[child]; 
			parent = child;
			child *= 2; 
		}
		heap[parent]= last;

		return max;
	}	

 

 

이러한 heap을 이용하면 정렬을 수행할 수 있다. 

 

1) minheap을 만들어서 값을 heap에 삽입하고 하나씩 삭제 O(logN) 한다.

2) 삭제된 노드를 새로운 배열에 차례대로 넣는다 . 

-> 이 과정이 노드의 길이 N번만큼 반복되므로 heap sort의 시간복잡도는 O(NlogN)이 된다.

이러한 heap sort가 가장 유리한 경우는 전체값을 sort할 때보다, 가장 작은 몇 개의 값, 가장 큰 몇개의 값만이 필요할 때이다.