Ccmmutty logo
Commutty IT
0 pv2 min read

Heaps

https://cdn.magicode.io/media/notebox/79fe49ea-b794-4deb-bb75-eb48fa557c1d.jpeg
ヒープ(英: heap)とは、「子要素は親要素より常に大きいか等しい(または常に小さいか等しい)」という制約を持つ木構造の事。単に「ヒープ」という場合、二分木を使った二分ヒープを指すことが多い。ヒープデータ構造は、選択、グラフ、k-wayマージアルゴリズムで使用されます。検索、マージ、挿入、キー変更、削除などの操作はヒープ上で行われます。ヒープは、Go の container/heap(なるほど、container/以下にいろんなデータの方が入っているのか) パッケージの一部です。ヒープ順序(最大ヒープ)プロパティによると、各ノードに格納されている値は、その子よりも大きいか同じです。
順序が降順(先頭から大きいもの順)ならmaximum heap、逆はminimum heap。
go
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()

Discussion

コメントにはログインが必要です。