알고리즘
[2. 정렬] Heap Sort (2)
이전 글에서 Heap Sort를 위해 필요한 Heap, Heapify 개념을 다루었다. Heap Sort는 배열이 주어졌을 때 다음과 같은 과정을 통해 정렬한다. ① 주어진 배열로 Max Heap을 만든다. ② Max Heapl에서 최대값(루트)를 가장 마지막 값과 바꾼다. (이때 가장 마지막 값은 정렬이 된 것이므로 힙의 일부가 아닌 것으로 간주함) ③ 루트노드에 대해서 Max-Heapify한다 ④ 남은 노드가 1개가 될 때 까지 ②,③을 반복한다 크게 생각한다면 Max Heap을 만들고(초기화), iterative하게 Max-Heapify하는 과정을 통해 배열을 정렬하는 것이다. 1. Heap Sort 과정 (1) Max Heap 만들기 정렬되지 않는 배열을 추상적으로 complete binary t..
