検索
ホームページバックエンド開発GolangGo言語で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] <p>上記のコードでは、MinHeap タイプを定義し、Len、Less、および Swap メソッドを実装します。 Len メソッドは最小ヒープ内の要素の数を返し、Less メソッドは 2 つの要素のサイズを比較し、Swap メソッドは 2 つの要素の位置を交換します。 </p><p>次に、最小限のヒープ初期化メソッドを実装する必要があります。 heap.Init 関数を使用して、空の最小ヒープを初期化できます。 </p><pre class="brush:php;toolbar:false">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]  0 {
        fmt.Printf("%d ", heap.Pop(h))
    }
}

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

概要

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

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

声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
Golang:Goプログラミング言語が説明しましたGolang:Goプログラミング言語が説明しましたApr 10, 2025 am 11:18 AM

GOのコア機能には、ガベージコレクション、静的リンク、並行性サポートが含まれます。 1. GO言語の並行性モデルは、GoroutineとChannelを通じて効率的な同時プログラミングを実現します。 2.インターフェイスと多型は、インターフェイスメソッドを介して実装されているため、異なるタイプを統一された方法で処理できます。 3.基本的な使用法は、関数定義と呼び出しの効率を示しています。 4。高度な使用法では、スライスは動的なサイズ変更の強力な機能を提供します。 5.人種条件などの一般的なエラーは、Getest Raceを通じて検出および解決できます。 6.パフォーマンス最適化Sync.Poolを通じてオブジェクトを再利用して、ゴミ収集圧力を軽減します。

Golangの目的:効率的でスケーラブルなシステムの構築Golangの目的:効率的でスケーラブルなシステムの構築Apr 09, 2025 pm 05:17 PM

GO言語は、効率的でスケーラブルなシステムの構築においてうまく機能します。その利点には次のものがあります。1。高性能:マシンコードにコンパイルされ、速度速度が速い。 2。同時プログラミング:ゴルチンとチャネルを介してマルチタスクを簡素化します。 3。シンプルさ:簡潔な構文、学習コストとメンテナンスコストの削減。 4。クロスプラットフォーム:クロスプラットフォームのコンパイル、簡単な展開をサポートします。

SQLソートのステートメントによる順序の結果がランダムに見えるのはなぜですか?SQLソートのステートメントによる順序の結果がランダムに見えるのはなぜですか?Apr 02, 2025 pm 05:24 PM

SQLクエリの結果の並べ替えについて混乱しています。 SQLを学習する過程で、しばしば混乱する問題に遭遇します。最近、著者は「Mick-SQL Basics」を読んでいます...

テクノロジースタックの収束は、テクノロジースタック選択のプロセスにすぎませんか?テクノロジースタックの収束は、テクノロジースタック選択のプロセスにすぎませんか?Apr 02, 2025 pm 05:21 PM

テクノロジースタックの収束とテクノロジーの選択の関係ソフトウェア開発におけるテクノロジーの選択、テクノロジースタックの選択と管理は非常に重要な問題です。最近、一部の読者が提案しています...

反射比較を使用し、GOの3つの構造の違いを処理する方法は?反射比較を使用し、GOの3つの構造の違いを処理する方法は?Apr 02, 2025 pm 05:15 PM

GO言語で3つの構造を比較および処理する方法。 GOプログラミングでは、2つの構造の違いを比較し、これらの違いを...

Goでグローバルにインストールされたパッケージを表示する方法は?Goでグローバルにインストールされたパッケージを表示する方法は?Apr 02, 2025 pm 05:12 PM

Goでグローバルにインストールされたパッケージを表示する方法は? GO言語で開発する過程で、GOはしばしば使用します...

Golandのカスタム構造ラベルが表示されない場合はどうすればよいですか?Golandのカスタム構造ラベルが表示されない場合はどうすればよいですか?Apr 02, 2025 pm 05:09 PM

Golandのカスタム構造ラベルが表示されない場合はどうすればよいですか?ゴーランドを使用するためにGolandを使用する場合、多くの開発者はカスタム構造タグに遭遇します...

See all articles

ホットAIツール

Undresser.AI Undress

Undresser.AI Undress

リアルなヌード写真を作成する AI 搭載アプリ

AI Clothes Remover

AI Clothes Remover

写真から衣服を削除するオンライン AI ツール。

Undress AI Tool

Undress AI Tool

脱衣画像を無料で

Clothoff.io

Clothoff.io

AI衣類リムーバー

AI Hentai Generator

AI Hentai Generator

AIヘンタイを無料で生成します。

ホットツール

Dreamweaver Mac版

Dreamweaver Mac版

ビジュアル Web 開発ツール

EditPlus 中国語クラック版

EditPlus 中国語クラック版

サイズが小さく、構文の強調表示、コード プロンプト機能はサポートされていません

WebStorm Mac版

WebStorm Mac版

便利なJavaScript開発ツール

SAP NetWeaver Server Adapter for Eclipse

SAP NetWeaver Server Adapter for Eclipse

Eclipse を SAP NetWeaver アプリケーション サーバーと統合します。

SublimeText3 Mac版

SublimeText3 Mac版

神レベルのコード編集ソフト(SublimeText3)