Heap Sort - 힙 정렬
Heap 자료구조를 이용한 정렬 방법입니다.
https://en.wikipedia.org/wiki/Heapsort
Heapsort - Wikipedia
From Wikipedia, the free encyclopedia Jump to navigation Jump to search A sorting algorithm which uses the heap data structure In computer science, heapsort is a comparison-based sorting algorithm. Heapsort can be thought of as an improved selection sort:
en.wikipedia.org
먼저 Heap Sort를 이해하려면 Heap 자료구조와 완전이진트리에 대해 이해해야 합니다.
자세한 내용은 아래 글에서 확인하는 게 좋을 것 같습니다.
https://ratsgo.github.io/data%20structure&algorithm/2017/09/27/heapsort/
힙 정렬(Heap Sort) · ratsgo's blog
이번 글에서는 힙(heap)이라는 자료구조와 힙 정렬(Heap Sort) 알고리즘에 대해 살펴보도록 하겠습니다. 이 글은 고려대 김황남 교수님과 역시 같은 대학의 김선욱 교수님 강의와 위키피디아를 정리하였음을 먼저 밝힙니다. 파이썬 코드 구현은 이곳을 참고하였습니다. 그럼 시작하겠습니다. 힙은 큰 키(우선 순위)에 자주 액세스하거나 키(우선 순위) 중심으로 정렬된 시퀀스를 활용해야 할 때 유용한 자료구조입니다. 힙은 한 노드(node)가 최대 두 개의 자
ratsgo.github.io
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 구조를 배열로 변환된 것을 그려봤습니다.
배열을 완전이진트리로 변환되는 과정을 그리면 이해하기 편합니다.