[알고리즘] 힙 정렬 Heap Sort (C++ 구현, make_heap, pop_heap)

📌 힙 정렬

힙 정렬은 1등을 뽑아내고 나머지 원소에서 계속 1등을 뽑아내는 정렬 알고리즘으로, 버블정렬과 비슷하다. 버블정렬은 1등(오름차순 정렬에서 가장 큰 수)을 뽑고 나서 이전의 1등들과 비교해야 한다. 그러나 힙정렬에서는 1등이 뽑힌 순서대로 다음은 자동으로 2등, 3등, ... 이렇게 되므로 1등을 뽑고 나서 추가적인 비교가 필요 없다. 매 라운드에서 한번 1등으로 뽑히면 그 원소는 이미 순서가 정해진 것이다. 남은 원소가 없을 때까지 반복적으로 1등을 뽑아내는 것이 핵심이다.

 

😶 버블정렬에 더 알아보고 싶다면 

2020/12/30 - [코딩테스트/알고리즘 & 자료구조] - [알고리즘] 버블정렬 Bubble Sort (C++ 구현)

[알고리즘] 버블정렬 Bubble Sort (C++ 구현)

---

1등을 뽑아내고 나머지에서 계속 1등을 뽑아내는 과정을 '힙' 자료구조를 이용해서 힙정렬이라 부른다. 힙이란 리프노드를 제외한 모든 노드의 자식이 반드시 2개인 일종의 완전 이진 트리이다. 완전이진트리에서 리프 노드가 어떤 노드 이후부터 모두 생략된 상태를 의미한다. 

• max heap : 부모노드 > 자식노드 (부모는 자식보다 반드시 크다)  → 오름차순 정렬에 적합
• min heap : 부모노드 < 자식노드 (부모는 자식보다 반드시 작다)

이러한 힙 자료구조는 배열로 표현할 수 있다. 완전이진트리이므로 단계별로 1, 2, 4, 8, 16, 32 ... 개씩 있으므로 배열로 나타낸다면 노드의 왼쪽 자식은 2i, 노드의 오른쪽 자식은 2i + 1 위치에 연속되게 배열에 저장된다.

힙으로 어떻게 정렬을 할까?

크기 n의 주어진 배열이 힙으로 변환되었다고 가정하자. max-heap 에서 제일 큰 원소는 루트노드이다. 힙에서 가장 큰 원소를 하나씩 꺼냄으로써 순서대로 정렬할 수 있다. 루트노드가 제거되면 이 자리에 가장 마지막 리프 노드를 가져온다. 가져온 노드 값과 원래 노드의 두 자식을 비교하여 가장 큰 값이 루트노드로 올라가도록 반복한다. 그럼 나머지 n-1개 중 1등인 루트노드를 또 꺼낸다. (전체 2등) 이렇게 반복하여 힙에서 모든 원소를 빼낸다.

 

이때 크기 n의 주어진 배열이 힙으로 변환되는 과정이 필요하지만 간단하게 c++의 algorithm 패키지에 있는 make_heap() 내장함수를 이용했다. algorithm 라이브러리 사용해도 되는지.. 모르겠지만 난 그냥 쓰겠어 코드가 너무 간단하지만..

• make_heap(begin, end) : 주어진 배열을 힙(max-heap)으로 변환
• pop_heap(begin, end) : 주어진 힙에서 첫번째 원소(루트 노드)를 꺼냄

// use make_heap function in algorithm library
// max heap 만들어서 루트 노드 하나씩 뽑아내기
vector<int> heapsort(vector<int> L) {
	make_heap(L.begin(), L.end()); 
    
	for (auto last = L.end(); last != L.begin(); last--) {
		pop_heap(L.begin(), last);
	}
	
	return L;
}

📌시간복잡도 (feat. 비교 기반 정렬 기법)

힙정렬의 시간복잡도는 역시나 nlogn을 가진다. 그리고 비교에 기반한 정렬의 시간복잡도는 모두 nlogn 보다 빠를 수 없다. 

증명과정은 복잡하고 제대로 이해하지 못한 거 같아 패스한다.. (언젠간 하겠지.. 미래의 나)

 

그래서 비교 기반의 정렬 기법 외에 더 효율적인 정렬기법이 있는지 살펴볼 필요가 있다. 시간복잡도가 줄어들면 보통 알고리즘이 이해하기 어렵거나 공간복잡도가 급증하는 경향이 있다. 다음엔 버킷, 계수, 기수 정렬에 대해 알아본다.