# go最大堆 实现字符串频率降序排列

## 题面

``"tree"``

``````"eert"
``````

‘e’出现两次，’r’和’t’都只出现一次。

## 大根堆

• 实现go 堆的 `heap.Interface` 接口
• 自定义依据重复次数实现最大堆排序规则
``````import (
"bytes"
"container/heap"
)

type ByteSliceHeap [][]byte
var _ heap.Interface = (*ByteSliceHeap)(nil)

func (h ByteSliceHeap) Len() int           { return len(h) }
func (h ByteSliceHeap) Less(i, j int) bool { return len(h[i]) > len(h[j]) }
func (h ByteSliceHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *ByteSliceHeap) Push(x interface{}) {
*h = append(*h, x.([]byte))
}
func (h *ByteSliceHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}

func frequencySort(s string) string {
m := make(map[byte][]byte, 0)
for i := 0; i < len(s); i++ {
if _, ok := m[s[i]]; !ok {
m[s[i]] = []byte{s[i]}
} else {
m[s[i]] = append(m[s[i]], s[i])
}
}
h := &ByteSliceHeap{}
for _, v := range m {
heap.Push(h, v)
}
buf := &bytes.Buffer{}
for h.Len() > 0 {
buf.Write(heap.Pop(h).([]byte))
}
return buf.String()
}``````

## topk 小根堆

``````func topKFrequent(nums []int, k int) []int {
occurrences := map[int]int{}
for _, num := range nums {
occurrences[num]++
}
h := &IHeap{}
heap.Init(h)
for key, value := range occurrences {
heap.Push(h, [2]int{key, value})
if h.Len() > k {
heap.Pop(h)
}
}
rs := make([]int, k)
for i := 0; i < k; i++ {
rs[k - i - 1] = heap.Pop(h).([2]int)[0]
}
return rs
}

type IHeap [][2]int

func (h IHeap) Len() int           { return len(h) }
func (h IHeap) Less(i, j int) bool { return h[i][1] < h[j][1] }
func (h IHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IHeap) Push(x interface{}) {
*h = append(*h, x.([2]int))
}

func (h *IHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}
``````

(=￣ω￣=)··· 暂无内容！

128

22

95

50