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로 구현된 코드입니다.

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)
}

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

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