[알고리즘][정렬][C/C++] Heap Sort (우선순위 큐)

---

 

Heap Sort (우선순위 큐) 특징

1. Tree 구조(완전이진트리)를 활용하는 알고리즘
2. Heap에 저장된 상태는 완전히 정렬된 상태가 아니고, Heap에서 Pop할 때, 정렬이 완성된다. 
3. 우선순위 큐 (정의된 우선순위에 따라 처리되는 큐) 를 Heap으로 보통 구현한다. 
4.  시간복잡도 : O(N*logN)
5. N 크기의 배열을 이용하여 구현한다. 

 

 

* 완전 이진트리 (Complete Binary Tree)
: 이진 트리의 원소가 왼쪽부터 채워지는 트리를 말한다. 
: 아래 그림 중, A, C, D에 해당

* Heap
: 아래 그림 중 A, D에 해당
: A는 Min Heap, D는 Max Heap

다음 중 Heap 구조인 것은?

 

 

* Heap 구조와 배열 Index의 관계

● Left Child Index = p * 2
● Right Child Index = p * 2 + 1
● Parent Index = p / 2

Heap 구조와 배열 Index의 관계

 

 

 

 

 

Heap Sort 과정 이해하기 - Push (MAX Heap)

MAX Heap Push는 아래의 과정으로 이루어진다. 

1. Heap의 마지막에 new Data를 넣는다. 
2. 부모 노드와 비교해서 자식 노드가 더 큰 경우, swap 한다. 
3. 마지막 노드 ~ 루트 노드까지 반복한다. 
4. 중간에 자식 노드가 더 작은 경우엔 중단한다. 

 

2, 1, 3, 6, 4, 5, 7 을 차례로 추가한다고 해보자. 

 

1. "2"를 Heap에 추가 한다. 

 

 

2. "1"을 추가한다. 부모 노드인 "2"와 비교했을 때, 부모 노드가 더 큰 값이므로 swap하지 않는다. 

3. "3"을 추가한다. 

 

4. 부모 노드인 "2"와 비교했을 때, 부모 노드가 더 작은 값이므로 swap 한다. 

 

 

 

5. "6"을 추가한다. 

 

6. 부모 노드인 "1"과 비교했을 때, 부모 노드가 더 작은 값이므로 swap 한다. 

 

7. 부모 노드인 "3"과 비교했을 때, 부모 노드가 더 작은 값이므로 swap 한다. 

 

 

 

8. 위 과정을 반복하여, 나머지 수들을 Push 한다. 

Heap Push (2, 1, 3, 6, 4, 5, 7) 결과

 

 

 

 

Heap Sort 과정 이해하기 - Pop (MAX Heap)

MAX Heap Pop은 아래의 과정으로 이루어진다. 

(0. MAX 값의 return이 필요한 경우, Heap의 루트 노드 값을 따로 저장해둔다. )
1. Heap의 루트 노드와 마지막 노드를 swap 하고, heap Size를 1개 줄인다. 
2. 부모 노드와 자식 노드를 비교하여, 자식 노드가 더 큰 경우, swap 한다. 
3. Left 자식 노드와 Right 자식 노드 중 더 큰 값을 부모 노드와의 비교 대상으로 한다. 
4. 루트 노드 ~ 마지막 노드까지 반복한다. 
5. 중간에 자식 노드가 더 작은 경우엔 중단한다. 

 

 

아까의 Heap에서 Pop을 해보자. 

 

 

1. Heap의 루트 노드와 마지막 노드를 swap 한다. 

 

 

2. heap Size를 1개 줄인다. 

3. 자식노드인 "6"과 비교했을 때, 자식 노드가 더 크므로, swap 한다. 

 

 

4. pop 완료

Heap Pop 결과

 

 

---

 

Heap Sort 코드 - Push

먼저, MAX Heap의 Push 함수 코드를 살펴보자. 

const int MAX = 1000;
int N;
int heap[MAX], heapSize;	// MAX Heap

void swap(int& a, int& b) {
	int t = a; a = b; b = t;
}

void push(int newData) {	
	heap[++heapSize] = newData; // heap의 맨 뒤에 New Data 추가
		
    	// c 값이 루트 노드 전까지 반복 (heap의 마지막 → 루트 노드)
	for (int c = heapSize; c > 1; c /= 2) {
		if (heap[c] > heap[c / 2])
			swap(heap[c], heap[c / 2]); // 부모 노드의 값보다 크다면 교환
		else break;
	}
}

 

Min Heap의 경우에는 부모 노드와 비교하는 부분의 부등호만 바꿔주면 된다. 

void push(int newData) {	
	heap[++heapSize] = newData; // heap의 맨 뒤에 New Data 추가
		
    	// c 값이 루트 노드 전까지 반복  (heap의 마지막 → 루트 노드)
	for (int c = heapSize; c > 1; c /= 2) {
		if (heap[c] < heap[c / 2])
			swap(heap[c], heap[c / 2]); // 부모 노드의 값보다 작다면 교환
		else break;
	}
}

 

 

Heap Sort 코드 - Pop

먼저, MAX Heap의 Pop 함수 코드를 살펴보자. 

const int MAX = 1000;
int N;
int heap[MAX], heapSize;	// MAX Heap

void swap(int& a, int& b) {
	int t = a; a = b; b = t;
}

void pop() {
	swap(heap[1], heap[heapSize--]);	// 루트 노드의 값을 heap의 마지막으로 이동

	// c 값이 heap 마지막 전까지 반복 (루트 노드 → heap의 마지막)
	for (int c = 2; c <= heapSize; c *= 2) {
		if (c < heapSize && heap[c + 1] > heap[c]) 
			c++;	// 왼쪽, 오른쪽 중 큰 값으로 대표 child 정하기
		
		if (heap[c] > heap[c / 2]) 
			swap(heap[c], heap[c / 2]);	// 부모 노드의 값보다 크다면 교환
		else break;
	}
}

 

Min Heap의 경우에는 대표 child 정하기 부분과 부모 노드와 비교하는 부분의 부등호만 바꿔주면 된다. 

void pop() {
	swap(heap[1], heap[heapSize--]);	// 루트 노드의 값을 heap의 마지막으로 이동

	// c 값이 heap 마지막 전까지 반복 (루트 노드 → heap의 마지막)
	for (int c = 2; c <= heapSize; c *= 2) {
		if (c < heapSize && heap[c + 1] < heap[c]) 
			c++;	// 왼쪽, 오른쪽 중 큰 값으로 대표 child 정하기
		
		if (heap[c] < heap[c / 2]) 
			swap(heap[c], heap[c / 2]);	// 부모 노드의 값보다 크다면 교환
		else break;
	}
}

 

 

Heap Sort 코드 - 전체

#include <stdio.h>

const int MAX = 1000;
int N;
int heap[MAX], heapSize; // MAX Heap

void swap(int& a, int& b) {
	int t = a; a = b; b = t;
}

void push(int newData) {	
	heap[++heapSize] = newData; // heap의 맨 뒤에 New Data 추가
		
    	// c 값이 루트 노드 전까지 반복 (heap의 마지막 → 루트 노드)
	for (int c = heapSize; c > 1; c /= 2) {
		if (heap[c] > heap[c / 2])
			swap(heap[c], heap[c / 2]); // 부모 노드의 값보다 크다면 교환
		else break;
	}
}

void pop() {
	swap(heap[1], heap[heapSize--]);	// 루트 노드의 값을 heap의 마지막으로 이동

	// c 값이 heap 마지막 전까지 반복 (루트 노드 → heap의 마지막)
	for (int c = 2; c <= heapSize; c *= 2) {
		if (c < heapSize && heap[c + 1] > heap[c]) 
			c++;	// 왼쪽, 오른쪽 중 큰 값으로 대표 child 정하기
		
		if (heap[c] > heap[c / 2]) 
			swap(heap[c], heap[c / 2]);	// 부모 노드의 값보다 크다면 교환
		else break;
	}
}

int main() {
	scanf("%d", &N);

	int newData;
	for (int i = 0; i < N; i++) {
		scanf("%d", &newData);
		push(newData);	// Heap Push
	}

	for (int i = 0; i < N; i++) {
		printf("%d ", heap[1]);	// MAX print
		pop();		// Heap Pop
	}

	return 0;
}

 

 

---

 

연습문제 추천

 

[Advanced][정올] 1318번 : 못생긴 수

[Advanced][정올] 1318번 : 못생긴 수

 

 

[Advanced][정올] 1190번 : 모두더하기

[Advanced][정올] 1190번 : 모두더하기