从Leetcode 每日一题练习继续讨论：
题解
本题是一道基础题, 要求手动实现一种排序方式进行排序, 之前已经实现过归并排序, 快排, 计数排序, 因此本次实现堆排序, 实现堆排序的关键在于构建一个最小堆.
代码
type IntHeap []int
func (h IntHeap) Len() int {
return len(h)
}
func (h IntHeap) Less(i, j int) bool {
return h[i] < h[j]
}
func (h IntHeap) Swap(i, j int) {
h[i], h[j] = h[j], h[i]
}
func (h *IntHeap) Push(x interface{}) {
*h = append(*h, x.(int))
}
func (h *IntHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}
func sortArray(nums []int) []int {
h := &IntHeap{}
heap.Init(h) // 初始化堆
// 将所有元素推入堆中
for _, num := range nums {
heap.Push(h, num)
}
sortedArray := make([]int, 0, len(nums))
for h.Len() > 0 {
sortedArray = append(sortedArray, heap.Pop(h).(int))
}
return sortedArray
}