Go言語でmin-heapを実装する方法

最小ヒープは、最小の要素をすばやく見つけることができるデータ構造です。 Go 言語では、ヒープ パッケージを使用して最小限のヒープを実装できます。この記事では、Go 言語で min-heap を実装する方法を詳しく説明します。

最小ヒープとは何ですか?

最小ヒープは、次の 2 つの条件を満たすバイナリ ツリー構造です。

1. 親ノードの値が子ノードの値以下である。
2. 各レベルは左から右に入力されます。

たとえば、次は最小ヒープです:

      2
    /   \
   5     3
  / \   / \
 7   6 8   4

最小ヒープでは、ルート ノードは常に最小の要素であるため、最小値を見つける時間計算量は次のようになります。お(1) 。最小ヒープの挿入および削除操作の時間計算量は O(log n) です。

最小ヒープを実装するにはどうすればよいですか?

Go 言語では、ヒープ パッケージを使用して最小限のヒープを実装できます。ヒープ パッケージは、最小ヒープを実装するための次の 3 つのメソッドを提供します。

1. Init: 空の最小ヒープを初期化します。
2. プッシュ: 要素を最小ヒープに挿入します。
3. Pop: 最小ヒープから最小の要素を削除して返します。

まず、要素を格納するためのデータ構造を定義する必要があります。今回は要素としてint型を使用します。 int 型を heap.Interface 型に変換する必要があるため、heap.Interface インターフェイスの 3 つのメソッド (Len、Less、および Swap) を実装する必要があります。

type MinHeap []int

func (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

上記のコードでは、MinHeap タイプを定義し、Len、Less、および Swap メソッドを実装します。 Len メソッドは最小ヒープ内の要素の数を返し、Less メソッドは 2 つの要素のサイズを比較し、Swap メソッドは 2 つの要素の位置を交換します。

次に、最小限のヒープ初期化メソッドを実装する必要があります。 heap.Init 関数を使用して、空の最小ヒープを初期化できます。

h := &MinHeap{}
heap.Init(h)

これで、空の最小ヒープが初期化されました。次に、heap.Push 関数を使用して要素を挿入します。

heap.Push(h, 2)
heap.Push(h, 5)
heap.Push(h, 3)
heap.Push(h, 7)
heap.Push(h, 6)
heap.Push(h, 8)
heap.Push(h, 4)

上記のコードでは、heap.Push 関数を使用して要素を最小ヒープに挿入します。

heap.Pop 関数を使用して、最小の要素を削除して返すこともできます。

for h.Len() > 0 {
     fmt.Printf("%d ", heap.Pop(h))
}

上記のコードでは、loop と heap.Pop 関数を使用して、最小ヒープ内のすべての要素を出力します。

完全なコード:

package main

import (
    "container/heap"
    "fmt"
)

type MinHeap []int

func (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *MinHeap) Push(x interface{}) {
    *h = append(*h, x.(int))
}

func (h *MinHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

func main() {
    h := &MinHeap{}
    heap.Init(h)

    heap.Push(h, 2)
    heap.Push(h, 5)
    heap.Push(h, 3)
    heap.Push(h, 7)
    heap.Push(h, 6)
    heap.Push(h, 8)
    heap.Push(h, 4)

    for h.Len() > 0 {
        fmt.Printf("%d ", heap.Pop(h))
    }
}

上記のコードでは、Len、Less、および Swap メソッドの実装に加えて、Push メソッドと Pop メソッドも実装します。 Push メソッドは要素を最小ヒープに挿入し、Pop メソッドは最小の要素を最小ヒープから削除して返します。

概要

この記事では、Go 言語で最小ヒープを実装する方法を紹介します。ヒープ パッケージによって提供される関数を使用すると、要素の挿入および削除時に O(log n) 時間計算量の最小ヒープを迅速に実装できます。他のタイプのヒープを実装する必要がある場合は、ヒープ パッケージのドキュメントを参照してください。

以上がGo言語でmin-heapを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。