堆排序——Go标准库堆，排序一个几乎有序的数组
package heap
import (
"container/heap"
"fmt"
"testing"
)
type IntHeap []int // 定义IntHeap类型
/*
实现container/heap 的接口
type Interface interface {
Push(x interface{}) // add x as element Len()
Pop() interface{} // remove and return element Len() - 1.
}
*/
func (h IntHeap) Len() int { return len(h) }
func (h IntHeap) Less(i, j int) bool {
return h[i] < h[j] // 如果h[i]<h[j]生成的就是小根堆，如果h[i]>h[j]生成的就是大根堆
}
func (h IntHeap) Swap(i, j int) {
h[i], h[j] = h[j], h[i]
}
func (h *IntHeap) Pop() interface{} { // 绑定pop方法，从最后拿出一个元素并返回
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}
func (h *IntHeap) Push(x interface{}) { // 绑定push方法，插入新元素
*h = append(*h, x.(int))
}
func TestGoHeapDemo(t *testing.T) {
iheap := &IntHeap{}
heap.Init(iheap) // 绑定类型
heap.Push(iheap,3)
heap.Push(iheap,1)
heap.Push(iheap,30)
heap.Push(iheap,3222)
heap.Push(iheap,34)
fmt.Println(heap.Pop(iheap))
fmt.Println(heap.Pop(iheap))
fmt.Println(heap.Pop(iheap))
fmt.Println(heap.Pop(iheap))
}
func SortArrayDistanceLessK(arr []int, k int) {
iHeap := &IntHeap{}
heap.Init(iHeap) // 绑定类型
index := 0
for ; index <= min(len(arr) - 1 , k ); index++ {
heap.Push(iHeap,arr[index])
}
i := 0
for ; index < len(arr); i, index = i + 1, index + 1 {
heap.Push(iHeap,arr[index]) //先加一个 再弹出 或先弹出再加都可以
arr[i] = heap.Pop(iHeap).(int)
}
for len(*iHeap) != 0 { //后面的几个值依次弹出就行了，沿途的可以一边加一边弹
arr[i] = heap.Pop(iHeap).(int)
i++
}
}
func min(a, b int) int {
if a > b {
return b
}
return a
}
func TestSortArrayDistanceLessK(t *testing.T) {
arr := []int{1,3,4,2,3,7,6,8,10,6,9}
SortArrayDistanceLessK(arr,3) //O(n * logk)
fmt.Println(arr)
}