container/heap パッケージ

4月 24

import "container/heap"

heap.Interfaceを実装している型すべてに、ヒープ操作を提供します。

heap.go

Init関数

func Init(h Interface)

ヒープは何らかのヒープ操作を行う前に初期化しなくてはなりません。このInit関数は何度呼び出しても常に同じ結果となる(冪等である)ため、ヒープの内容の順序が壊れたときは何回でも呼び出せます。この計算量はn = h.Len()として、O(n*log(n))になります。

func Pop(h Interface) interface{}

Popは、ヒープの最小値である要素を削除し、その削除した要素を返します。この計算量はn = h.Len()として、O(log(n))になります。Remove(h, 0)と同じです。

func Push(h Interface, x interface{})

Pushは、パラメータxを新たな要素としてヒープに格納します。この計算量はn = h.Len()として、O(log(n))になります。

func Remove(h Interface, i int) interface{}

Removeは、パラメータiで指定した位置の要素をヒープから削除します。この計算量はn = h.Len()として、O(log(n))になります。

このheap.Interfaceを実装した型はすべて、下の不変量をもつ最小ヒープとして使用可能(Initの呼び出し後)です。

!h.Less(j, i) for 0 <= i < h.Len() and j = 2*i+1 or 2*i+2 and j < h.Len()

type Interface interface {
    sort.Interface
    Push(x interface{})
    Pop() interface{}
}