heap_and_sort.go

package main

import (
        "fmt"
        "sort"
        "container/heap"
        "rand"
)

type record struct {
        position, value int
}

type list []record

func (l list) Len() int {
        return len(l)
}

func (l list) Swap(i, j int) {
        l[i], l[j] = l[j], l[i]
}

func (l *list) Pop() interface{} {
        v := (*l)[len(*l)-1]
        *l = (*l)[:len(*l)-1]
        return v
}

func (l *list) Push(x interface{}) {
        *l = append(*l, x.(record))
}

type posSorter struct {
        *list
}

func (s posSorter) Less(i, j int) bool {
        return (*s.list)[i].position < (*s.list)[j].position
}

type valSorter struct {
        *list
}

func (s valSorter) Less(i, j int) bool {
        return (*s.list)[i].value < (*s.list)[j].value
}

func main() {
        var a list
        heap.Init(posSorter{&a}) // not really necessary for empty a
        for i := 0; i < 10000; i++ {
                heap.Push(posSorter{&a}, record{rand.Int(), rand.Int()})
                if len(a) > 100 {
                        heap.Pop(posSorter{&a})
                }
        }
        sort.Sort(valSorter{&a})
        for _, i := range a {
                fmt.Println(i.value)
        }
}