How to build heap upon custom type

user_15468170 0
Viewed 96

I have a KeyValue type which looks like here:

type KeyValue struct {
    Key   string
    Value string
}

Since I want to build a heap over it, I defined a ByKey type and implements the heap.Interface 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
}

But when I run a test, the container/heap does not work. My test code is here:

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)

And the output is:

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}]

Unfortunately the kv1 is not sorted by key. I think there should be something wrong in functions like Swap(), Push() or Pop(). Any help is appreciated.

go heap data-structures containers
1 Answers

According to the docs:

A heap is a common way to implement a priority queue. To build a priority queue, implement the Heap interface with the (negative) priority as the ordering for the Less method, so Push adds items while Pop removes the highest-priority item from the queue. The Examples include such an implementation; the file example_pq_test.go has the complete source.

Try to heap.Pop a value:

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

user_80306510
Related