Heap Sort - 힙 정렬

Heap 자료구조를 이용한 정렬 방법입니다.

https://en.wikipedia.org/wiki/Heapsort

Heapsort - Wikipedia

먼저 Heap Sort를 이해하려면 Heap 자료구조와 완전이진트리에 대해 이해해야 합니다.
자세한 내용은 아래 글에서 확인하는 게 좋을 것 같습니다.

https://ratsgo.github.io/data%20structure&algorithm/2017/09/27/heapsort/

힙 정렬(Heap Sort) · ratsgo's blog

Go로 구현된 코드입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
package main
import "fmt"
// 입력값으로 받은 배열을 heap 구조로 만들어 줍니다.
func sift(arr []int, i int, arrLen int) []int {
    done := false
    maxChild := 0
    for (i*2+1 < arrLen) && (!done) {
        if i*2+1 == arrLen-1 {
            maxChild = i*2 + 1
        } else if arr[i*2+1] > arr[i*2+2] {
            // 왼쪽 자식노드의 인덱스를 확인합니다.
            maxChild = i*2 + 1
        } else {
            // 오른쪽 자식조드의 인덱스를 확인합니다.
            maxChild = i*2 + 2
        }
        fmt.Println(i, maxChild)
        if arr[i] < arr[maxChild] {
            arr[i], arr[maxChild] = arr[maxChild], arr[i]
            i = maxChild
        } else {
            done = true
        }
    }
    return arr
}
func main() {
    arr := []int{9, 1, 2, 8, 6, 7, 5, 3, 0, 4}
    fmt.Println("Initial array is:", arr)
    fmt.Println("")
    i := 0
    // 입력된 배열을 완전이진트리(배열)로 변환합니다.
    for i = len(arr)/2 - 1; i >= 0; i-- {
        arr = sift(arr, i, len(arr))
    }
    // arr: [9 8 7 3 6 2 5 1 0 4]
    // 완전이진트리(배열)의 최상위 heap(arr[0])부터 뒷쪽으로 이동하면서 정렬합니다.
    for i = len(arr) - 1; i >= 1; i-- {
        arr[0], arr[i] = arr[i], arr[0]
        arr = sift(arr, 0, i)
    }
    fmt.Println("Sorted array is: ", arr)
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

저는 heap 구조를 이해하기 위해 heap 구조를 배열로 변환된 것을 그려봤습니다.

배열을 완전이진트리로 변환되는 과정을 그리면 이해하기 편합니다.