堆定制——1.0强耦合版
package heap
import (
"encoding/json"
"fmt"
"testing"
)
//什么时候需要手写堆，需要更新堆中的某些值，让他自然有序
//迪杰斯特拉算法 就需要这类算法
// 从每个节点扫一遍， 代价会非常高
// 用户：可能对于某一个已经存在的对象，修改值， 在堆上找到，调整到该去的位置，logN级别
type student struct {
Name string
Age int
Height int
Weight int
}
type MyHeap struct {
heap []*student
indexMap map[*student]int //任何一个样本，记录在堆上的位置
heapSize int
comparator func(a, b *student) bool //比大小
}
func (my *MyHeap)String() string {
byte,_ := json.MarshalIndent(my.heap,"\t"," ")
return string(byte)
}
func NewMyHeap(com func(a, b *student) bool ) *MyHeap {
return &MyHeap{
heap: []*student{},
indexMap: map[*student]int{},
heapSize: 0,
comparator: com,
}
}
func (my *MyHeap) IsEmpty() bool {
return my.heapSize == 0
}
func (my *MyHeap) Size() int {
return my.heapSize
}
func (my *MyHeap)contains(key *student) bool {
_, ok := my.indexMap[key]
return ok
}
func (my *MyHeap)push(value *student) {
my.heap = append(my.heap, value)
my.indexMap[value] = my.heapSize
my.heapInsert(my.heapSize)
my.heapSize++
}
func (my *MyHeap)pop() *student {
ans := my.heap[0]
end := my.heapSize - 1
my.swap(0,end)
my.heap = my.heap[0:end]
delete(my.indexMap,ans)
my.heapSize--
my.heapify(0,my.heapSize)
return ans
}
func (my *MyHeap)heapInsert(index int){
for my.comparator(my.heap[index],my.heap[(index -1) /2]) {
my.swap(index,(index - 1) / 2)
index = (index - 1) / 2
}
}
func (my *MyHeap)resign(val *student) {
valueIndex := my.indexMap[val]
my.heapInsert(valueIndex) //上行或下行，两个分支 只会中一个
my.heapify(valueIndex,my.heapSize) //都不中就出去，可以实现重复加入值，按引用传递的话
}
func (my *MyHeap)heapify(index, heapSize int) {
leftChild := 2 * index + 1
for leftChild < heapSize {
best := leftChild //下沉
if leftChild + 1 < heapSize && my.comparator(my.heap[best + 1], my.heap[best]) {
best = leftChild + 1
}
if !my.comparator(my.heap[best],my.heap[index]) {
break
}
my.swap(index,best)
index = best
leftChild = 2 *index + 1
}
}
func (my *MyHeap)swap(i, j int) { //强同步
my.heap[i], my.heap[j] = my.heap[j],my.heap[i]
my.indexMap[my.heap[i]],my.indexMap[my.heap[j]] = my.indexMap[my.heap[j]],my.indexMap[my.heap[i]]
}
func TestMyHeap(t *testing.T) {
heap := NewMyHeap(func(a, b *student) bool { // 条件要统一
if a == b {
return false
}
if a.Age > b.Age {
return true
}
if a.Age == b.Age {
return a.Height > b.Height //年龄相同根据身高排序
}
return false // <
})
students := []student{
{
Name: "五零",
Age: 50,
Height: 190,
Weight: 130,
},
{
Name: "张三",
Age: 40,
Height: 160,
Weight: 100,
},
{
Name: "李四",
Age: 15,
Height: 100,
Weight: 110,
},
{
Name: "王五",
Age: 19,
Height: 190,
Weight: 190,
},
{
Name: "李六",
Age: 19,
Height: 180,
Weight: 170,
},
}
heap.push(&students[0])
heap.push(&students[1])
heap.push(&students[2])
heap.push(&students[3])
heap.push(&students[4])
students[0].Age = 7
heap.resign(&students[0]) //中途修改了某个值
//(heap)
for !heap.IsEmpty() {
fmt.Println(heap.pop())
}
}