힙 (Heap)

글에 앞서... 스택/큐에 대해서 다루고, 트리에 대해서 다뤄야 하지만...

순전히 자기 공부를 위한 블로그라는 핑계를 대고 작성하지 않았다 ^^ 공부는 했지만 스택/큐는 영 만들 마음이 안생기네

 

하지만 Heap은 중요하니 다루고 가겠다. 

힙은 일종의 트리인데, 부모노드의 값이 언제나 크거나, 언제나 작은 경우에만 작아야 한다는 규칙을 가지고 있다.

 

Min Heap: 부모 노드가 자식 노드보다 작다. 루트 노드값이 최솟값이다.

Max Heap: 부모 노드가 자식 노드보다 크다. 루트 노드값이 최댓값이다.

(전에 쓰던 블로그에서 옮김)

 

한 가지 알아야 할 것은 힙은 배열을 기반으로 구현하는 것이 원칙이다. 

스택, 큐, 덱 등과 같이 연결리스트로도 구현할 수 있는 것들과 다르게 안되는 이유는 

새 노드를 마지막 위치에 추가하는 것이 어렵다는 이유이다.

사실 간단하게 생각해봐도 링크드리스트 구조로 만들려면, 노드에 leftChild, rightChild, parent까지 

다 들어가 있어야하니 메모리도 많이먹고, 여러므로 안타까운 구조이다. 

(정말 많은 양의 데이터를 저장해야하는 트리 구조라면 전체 배열값을 정해놓고 사용해야하나..? ex) 서버.. 등)

void BuildMinHeap(int *arr,int cnt){
	for (int i = cnt/2; i > 0; i--)
		MinHeapify(arr, cnt, i);
}
void MinHeapify(int *arr, int cnt,int idx) {
	int left = idx * 2;
	int right = idx * 2 + 1;
	int smallest;
	int temp;
	if (left <= cnt && arr[left]<arr[idx])
		smallest = left;
	else
		smallest = idx;
	if (right <= cnt && arr[right]<arr[smallest])
		smallest = right;
	if (smallest != idx) {
		Swap(&arr[smallest], &arr[idx]);
		MinHeapify(arr, cnt, smallest);
	}
	else
		return;
}
void Heapsort(int *arr, int cnt) {
	BuildMinHeap(arr, cnt);
	int cnt2 = cnt;
	for (int i = cnt; i >= 1; i--) {
		Swap(&arr[1], &arr[i]);
		cnt--;
		MinHeapify(arr, cnt,1);
	}
}

먼저 이 코드는 최소힙을 이용해서 오름차순을 만드는 과정이다.

​

1. 배열 구조로 최소힙을 만든다. (MinHeapify)

2. 루트 노드값과 힙의 마지막 값의 위치를 바꾸어준다.

3. 힙의 size를 하나 줄여서, 마지막 값이 고정되게 한다.

4. (1~3) 과정을 반복한다.

 

MinHeapify는 자신과 자기의 자식노드를 대소비교하고, 더 작은 경우 바꾸는 행위는 재귀적으로 한다. 최종적으로는 한 노드가 자신의 위치를 찾을 때까지 반복한다.

 

BuildMinHeap은 개개의 서브트리의 루트노드부터 MinHeapify를 하는 과정을 한다.

heap size의 절반에 해당하는 index는 전체 힙에서의 마지막 서브트리 (높이가 1인 트리) 의 루트노드이다. 즉 모든 서브트리의 루트 노드를 건드리면서 MinHeapify 한다.