Go言語 ヒープの使い方メモ

随分前にやって忘れかけているのでメモ代わりに覚えてる分だけ書く．
あんまり良く分かってないので最低限使える分だけテキトーに．

container/heapパッケージではヒープを扱う関数がある．たぶん自分定義の型とかに使いやすいのだと思う．intとか元々あるやつはvector.IntVectorとかsortパッケージの方がいいのかどうかはわからない．
適当に使い方．

package main

import (
  "container/heap"
  "container/vector"
  "fmt"
)

type MyScore struct{
  id, score int
}

func (s MyScore) Less(o interface{}) bool {
  return s.score < o.(MyScore).score
}

func main(){
  v := new(vector.Vector)
  heap.Init(v)
  heap.Push(v, MyScore{1,2})
  heap.Push(v, MyScore{10,1})
  fmt.Println(heap.Pop(v))
  fmt.Println(heap.Pop(v))
}

出力

{10 1}
{1 2}

よくわからないけどvectorの場合はvector.LessInterfaceを実装する，つまり自分定義の型から使うLess関数があればいいようで．比較は，呼び出す側が小さいと真を返すようにすればいいみたい．PriorityQueueとかはこれを使えば実装できるっぽい．詳しいことはまだ調べてないor忘れた．