・2 min read
Heaps
ヒープ（英: heap）とは、「子要素は親要素より常に大きいか等しい（または常に小さいか等しい）」という制約を持つ木構造の事。単に「ヒープ」という場合、二分木を使った二分ヒープを指すことが多い。ヒープデータ構造は、選択、グラフ、k-wayマージアルゴリズムで使用されます。検索、マージ、挿入、キー変更、削除などの操作はヒープ上で行われます。ヒープは、Go の 
container/heap（なるほど、container/以下にいろんなデータの方が入っているのか） パッケージの一部です。ヒープ順序（最大ヒープ）プロパティによると、各ノードに格納されている値は、その子よりも大きいか同じです。
順序が降順（先頭から大きいもの順）ならmaximum heap、逆はminimum heap。
import (
"container/heap"
"fmt" )
// integerHeap a type
type IntegerHeap []int
// IntegerHeap method - gets the length of integerHeap
func (iheap IntegerHeap) Len() int { return len(iheap) }
// IntegerHeap method - checks if element of i index is less than j index
func (iheap IntegerHeap) Less(i, j int) bool { return iheap[i] < iheap[j] }
// IntegerHeap method -swaps the element of i to j index
func (iheap IntegerHeap) Swap(i, j int) { iheap[i], iheap[j] = iheap[j],
iheap[i] }
//IntegerHeap method -pushes the item
func (iheap *IntegerHeap) Push(heapintf interface{}) {
*iheap = append(*iheap, heapintf.(int))
}
//IntegerHeap method -pops the item from the heap
func (iheap *IntegerHeap) Pop() interface{} {
var n int
var x1 int
var previous IntegerHeap = *iheap
n = len(previous)
x1 = previous[n-1]
*iheap = previous[0 : n-1]
return x1
}
func main(){
var intHeap *IntegerHeap = &IntegerHeap{1,4,5}
heap.Init(intHeap)
heap.Push(intHeap, 2)
fmt.Printf("minimum: %d\n", (*intHeap)[0])
for intHeap.Len() > 0 {
fmt.Printf("%d \n", heap.Pop(intHeap))
}
}
main()
