정렬 알고리즘(Sorting Algorithm)의 모든 것 ④ - 힙 정렬(Heap Sort)

4. 정렬 알고리즘(Sorting Algorithm)의 모든 것 - 힙 정렬(Heap Sort)

 : 힙 정렬이란, 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법으로서, 내림차순 정렬을 위해서는 최대 힙을 구성하고, 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다.

** 잠깐의 자료구조 지식, Heap이란?

-> 힙이란, 최소값이나 최대값을 빠르게 찾아내기 위해(우선순위 큐) 완전 이진 트리를 기반으로 하는 트리 구조를 갖는 자료구조이다.

<< 힙 정렬 알고리즘 >>

1. n개의 노드에 대한 완전 이진 트리를 구성한다. 이때 루트 노드부터 부모 노드, 왼쪽 자식 노드, 오른쪽 자식 노드 순으로 구성한다.

2. 최대 힙을 구성한다. 최대 힙이란 부노드가 자식 노드보다 큰 트리를 말하는데, 단말 노드를 자식 노드로 가진 부모 노드부터 구성하며 아래부터 루트까지 올라오며 순차적으로 만들어 갈 수 있다.

3. 가장 큰 수(루트에 위치)를 가장 작은 수와 교환한다.

4. 2와 3을 반복한다.

-> 힙 생성 알고리즘은, 특정한 '하나의 노드'에 대해 수행하고, 특정한 노드의 두 자식 중에서 더 큰 자식과 자신의 위치를 바꿔가며 정렬한다.

<< 힙 정렬 C++ 기준 코드 >>