Fragment Description:



A heap basically stores a tree structure in a slice, so it’s sorted in a way the heap package understands.
When you Pop items from the heap, they come off in the correct order.
Nota Bene:
Unlike the other two types in the container package (which implement their own actual container type), the heap package is just a set of functions operating on an interface.
This means you get to deal with your own datatype.
Just implement sort.Interface (three methods) and heap.Interface (two methods) and you can start dealing with your container as a heap.
Keep in mind that when you print out the raw heap (if you base the heap off a slice like implemented here) it won’t be sorted.
By Daniel Huckstep, from the ebook 'Go, the standard library' (MIT License).


containerHeap

Go Playground

Last update, on 2015, Fri 9 Oct, 16:15:32

/* ... <== see fragment description ... */

package main

// type heap.Interface interface {
// sort.Interface
// // add x as element Len()
// Push(x interface{})
// // remove and return element Len() - 1.
// Pop() interface{}
// }
//
// type sort.Interface interface {
// // Len is the number of elements in the collection.
// Len() int
// // Less returns whether the element with index i should sort
// // before the element with index j.
// Less(i, j int) bool
// // Swap swaps the elements with indexes i and j.
// Swap(i, j int)
// }
import (
    "container/heap"
    "fmt"
    "math/rand"
)

type IntHeap []int

func (h IntHeap) Len() int {
    return len(h)
}
func (h IntHeap) Less(i, j int) bool {
    return h[i] < h[j]
}
func (h IntHeap) Swap(i, j int) {
    h[i], h[j] = h[j], h[i]
}
func (h *IntHeap) Push(v interface{}) {
    a := *h
    a = append(a, v.(int))
    *h = a
}
func (h *IntHeap) Pop() interface{} {
    a := *h
    n := len(a)
    v := a[n-1]
    *h = a[0 : n-1]
    return v
}
func main() {
    h := make(IntHeap, 0)
    fmt.Printf("init IntHeap: %v\n", h)
    for i := 0; i < 5; i++ {
        heap.Push(&h, rand.Intn(10))
    }
    // is not sorted
    fmt.Printf("unsorted IntHeap: %v\n===\n", h)
    l := h.Len()
    ints := make([]int, 0, l)
    for i := 0; i < l; i++ {
        ints = append(ints, heap.Pop(&h).(int))
        fmt.Printf("pass %d\n", i)
        // is sorted
        fmt.Printf("ints: %v\n", ints)
        // is drained
        fmt.Printf("IntHeap: %v\n====\n", h)
    }
}

/*
init IntHeap: []
unsorted IntHeap: [1 1 7 9 7]
===
pass 0
ints: [1]
IntHeap: [1 7 7 9]
====
pass 1
ints: [1 1]
IntHeap: [7 7 9]
====
pass 2
ints: [1 1 7]
IntHeap: [7 9]
====
pass 3
ints: [1 1 7 7]
IntHeap: [9]
====
pass 4
ints: [1 1 7 7 9]
IntHeap: []
====
*/



Comments