Google's Go Guide

import "container/heap"

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

パッケージファイル

heap.go

Init関数

func Init(h Interface)

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

Pop関数

func Pop(h Interface) interface{}

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

Push関数

func Push(h Interface, x interface{})

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

Remove関数

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

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

Interface型

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

h.Less(i, j) 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{};
}