힙 정렬 (heap sort)

힙(heap)을 이용하여 데이터를 정렬해보자. Heap은 complete binary tree이면서 모든 부모-자식 노드 간의 순서 관계가 일정한 자료구조이다. Heap을 이용하여 오름차순 정렬을 하는 경우,

1. 전체 데이터를 max-heap으로 재구성
2. 첫 데이터와 heap의 마지막 데이터를 교환
3. heap의 크기를 하나 감소시킴
4. heap 재구성
5. heap크기가 1보다 큰 경우 2~4 단계 반복

의 과정을 수행한다. Max heap을 구성하였으므로, heap의 첫번째 원소는 heap에 있는 나머지 원소보다 크거나 같다. 이 원소를 heap의 마지막 원소와 교환을하고, heap의 크기를 하나 줄이면, heap에 있던 데이터중 가장 큰 값이 heap 영역의 바로 다음에 위치하게 된다. 이 작업을 나머지 데이터에 반복하여 데이터를 정렬한다.

package main

import "fmt”

func main() {

    data := []int{5, 7, 1, 2, 10, 6, 4, 9, 8, 3}

    heapSort(data)

    fmt.Println(data)

}

type Comparer func(a, b int) bool

func heapSort(data []int) {

    compFunc := func(a, b int) bool {

        return a > b

    }

    buildHeap(data, len(data), compFunc)

    for size := len(data); size > 1; {

        data[0], data[size-1] = data[size-1], data[0]

        size--

        heapify(data, size, 0, compFunc)

    }

}

func buildHeap(data []int, size int, compFunc Comparer) {

    for index := (size - 2) / 2; index >= 0; index-- {

        heapify(data, size, index, compFunc)

    }

}

func heapify(data []int, size, index int, compFunc Comparer) {

    left := index*2 + 1

    right := left + 1

    sel := right

    if right < size {

        if compFunc(data[left], data[right]) {

            sel = left

        }

    } else if left < size {

        sel = left

    } else {

        return

    }

    if compFunc(data[sel], data[index]) {

        data[index], data[sel] = data[sel], data[index]

        heapify(data, size, sel, compFunc)

    }

}