时间戳

首页 > 解决方案 > 如何在自定义类型上构建堆

go - 如何在自定义类型上构建堆

问题描述

我有一个 KeyValue 类型，如下所示：

type KeyValue struct {
    Key   string
    Value string
}

由于我想在它上面构建一个堆，所以我定义了一个 ByKey 类型并实现了heap.Interface接口

type ByKey []KeyValue

func (a ByKey) Len() int           { return len(a) }
func (a ByKey) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
func (a ByKey) Less(i, j int) bool { return a[i].Key < a[j].Key }
func (a *ByKey) Push(x interface{}) {
    *a = append(*a, x.(KeyValue))
}
func (a *ByKey) Pop() interface{} {
    old := *a
    n := len(old)
    x := old[n-1]
    *a = old[0 : n-1]
    return x
}

但是当我运行测试时，容器/堆不起作用。我的测试代码在这里：

dic := []string{"1", "2", "3", "4", "5", "6", "7", "8", "9"}
generate := func(min, max int) *ByKey {
    n := rand.Intn(max - min) + min
    kvs := make(ByKey, 0)
    for i := 0; i < n; i++ {
        idx := rand.Intn(len(dic))
        kvs = append(kvs, KeyValue{
            Key:   dic[idx],
            Value: "1",
        })
    }
    return &kvs
}
    
kv1 := generate(10, 15)
fmt.Printf("before heapify kv1: %v\n", *kv1)

heap.Init(kv1)
fmt.Printf("after heapify kv1: %v\n", *kv1)

输出是：

before heapify kv1: [{7 1} {3 1} {3 1} {5 1} {7 1} {8 1} {9 1} {5 1} {7 1} {6 1} {8 1}]
after heapify kv1: [{3 1} {5 1} {3 1} {5 1} {6 1} {8 1} {9 1} {7 1} {7 1} {7 1} {8 1}]

不幸的kv1是，它不是按键排序的。Swap()我认为,Push()或等函数应该有问题Pop()。任何帮助表示赞赏。

标签： godata-structurescontainersheap

解决方案

根据文档：

堆是实现优先级队列的常用方法。要构建优先级队列，请实现具有（负）优先级的 Heap 接口作为 Less 方法的排序，因此 Push 添加项目，而 Pop 从队列中删除最高优先级的项目。示例包括这样的实现；文件 example_pq_test.go 有完整的源代码。

尝试heap.Pop一个值：

for kv1.Len() > 0 {
    fmt.Printf("%d ", heap.Pop(kv1))
}

{3 1}
{3 1}
{5 1}
{5 1}
{6 1}
{7 1}
{7 1}
{7 1}
{8 1}
{8 1}
{9 1}

PLAYGROUND

推荐阅读