概要
毎分飛行機が離着陸する賑やかな空港を想像してみてください。 航空管制官が緊急度に基づいてフライトに優先順位を付けるのと同じように、ヒープは特定の基準に基づいてデータを管理および処理するのに役立ち、最も「緊急」または「重要」なデータが常に上位にアクセスできるようにします。
このガイドでは、ヒープを根本から理解する旅に乗り出します。 まず、ヒープとは何か、そしてその固有の特性をわかりやすく説明することから始めます。 そこから、Python 独自のヒープ実装について詳しく見ていきます。
heapq
モジュールを使用して、その豊富な機能セットを探索してください。 したがって、優先度が最も高い (または最も低い) 要素が頻繁に必要となる動的データ セットを効率的に管理する方法を考えたことがあるなら、きっと役に立つでしょう。
ヒープとは何ですか?
ヒープの使用法に入る前に、まず理解しておきたいことは次のとおりです。 ヒープとは何ですか。 ヒープは、データ構造の世界でツリーベースの強力な手段として際立っており、特に次の点に優れています。 秩序と階層を維持する。 素人目には二分木に似ているかもしれませんが、その構造と管理ルールの微妙な違いが明らかに異なります。
ヒープの特徴の XNUMX つは、ヒープの性質です。 完全な二分木。 これは、おそらく最後のレベルを除いて、ツリーのすべてのレベルが完全に埋め尽くされていることを意味します。 この最後のレベル内では、ノードが左から右に配置されます。 このような構造により、配列またはリストを使用してヒープを効率的に表現および操作できるようになり、配列内の各要素の位置がツリー内の配置を反映するようになります。
しかし、ヒープの本当の本質は、その中にあります。 発注。 で 最大ヒープ、指定されたノードの値はその子の値を超えるか等しく、最大の要素がルートの右に配置されます。 一方、 最小ヒープ は逆の原則に基づいて動作します。つまり、どのノードの値もその子の値以下になり、最小の要素がルートに配置されるようになります。
アドバイス: ヒープを次のように視覚化できます。 数字のピラミッド。 最大ヒープの場合、ベースからピークに上がるにつれて数値が増加し、頂点で最大値になります。 対照的に、最小ヒープはピークの最小値から始まり、下に進むにつれて数値が増加します。
作業を進めるにつれて、ヒープのこれらの固有の特性がどのようにして効率的な操作を可能にするのか、そして Python がどのように機能するのかをさらに深く掘り下げていきます。 heapq
モジュールは、ヒープをコーディング作業にシームレスに統合します。
ヒープの特徴とプロパティ
ヒープは、その独自の構造と順序付け原理により、一連の明確な特性とプロパティをもたらし、さまざまな計算シナリオで非常に貴重なものになります。
何よりもまず、ヒープは 本質的に効率的。 ツリーベースの構造、特に完全なバイナリ ツリー形式により、優先要素 (最大または最小) の挿入や抽出などの操作を対数時間で実行できるようになります。 O(log n)。 この効率は、優先要素への頻繁なアクセスを必要とするアルゴリズムやアプリケーションにとって有益です。
ヒープのもう XNUMX つの注目すべき特性は、 メモリ効率。 ヒープは子ノードまたは親ノードへの明示的なポインタを必要とせずに配列またはリストを使用して表現できるため、スペースが節約されます。 配列内の各要素の位置はツリー内の配置に対応するため、予測可能で簡単なトラバースと操作が可能になります。
最大ヒープまたは最小ヒープのいずれであっても、ヒープの順序付けプロパティにより、次のことが保証されます。 ルートは常に最も優先度の高い要素を保持します。 この一貫した順序により、構造全体を検索することなく、最優先の要素に素早くアクセスできるようになります。
さらに、ヒープは 多才な。 バイナリ ヒープ (各親に最大 XNUMX つの子を持つ) が最も一般的ですが、ヒープは XNUMX つ以上の子を持つように一般化できます。 d-ary ヒープ。 この柔軟性により、特定の使用例やパフォーマンス要件に基づいた微調整が可能になります。
最後に、ヒープは 自動調整。 要素が追加または削除されるたびに、構造はそのプロパティを維持するために再配置されます。 この動的なバランシングにより、ヒープは常にそのコア操作に対して最適化された状態に保たれます。
アドバイス: これらの特性により、ヒープ データ構造は効率的な並べ替えアルゴリズム (ヒープ ソート) に適したものになりました。 Python でのヒープ ソートの詳細については、こちらをお読みください。 「Python でのヒープソート」 記事。
Python の実装と実際のアプリケーションを深く掘り下げると、ヒープの真の可能性が目の前に明らかになります。
ヒープの種類
すべてのヒープが同じように作成されるわけではありません。 ヒープはその順序と構造特性に応じてさまざまなタイプに分類でき、それぞれに独自の用途と利点があります。 XNUMX つの主要なカテゴリは次のとおりです 最大ヒープ および 最小ヒープ.
最も際立った特徴は、 最大ヒープ つまり、特定のノードの値がその子の値以上であるということです。 これにより、ヒープ内の最大の要素が常にルートに存在するようになります。 このような構造は、特定の優先キューの実装のように、最大要素に頻繁にアクセスする必要がある場合に特に便利です。
最大ヒープに相当するもの、 最小ヒープ 指定されたノードの値がその子の値以下であることを保証します。 これにより、ヒープの最小要素がルートに配置されます。 最小ヒープは、リアルタイム データ処理を扱うアルゴリズムなど、最小限の要素が最も重要であるシナリオでは非常に貴重です。
これらの主なカテゴリに加えて、ヒープは分岐要素に基づいて区別することもできます。
バイナリ ヒープが最も一般的で、各親には最大でも XNUMX つの子がありますが、ヒープの概念は XNUMX つ以上の子を持つノードに拡張できます。 で d-aryヒープ、各ノードには最大でも d
子供たち。 このバリエーションは、特定の操作を高速化するためにツリーの高さを下げるなど、特定のシナリオに合わせて最適化できます。
二項ヒープ は、再帰的に定義される二項ツリーのセットです。 二項ヒープは優先キューの実装で使用され、効率的なマージ操作を提供します。
有名なフィボナッチ数列にちなんで名付けられました。 フィボナッチヒープ バイナリ ヒープまたは二項ヒープと比較して、多くの操作の実行時間が短縮されます。 これらは、ネットワーク最適化アルゴリズムで特に役立ちます。
Python のヒープ実装 – ヒープク モジュール
Python は、ヒープ操作用の組み込みモジュールを提供します。 heapq
モジュール。 このモジュールは、開発者がカスタム実装を必要とせずにリストをヒープに変換し、さまざまなヒープ操作を実行できるようにするヒープ関連関数のコレクションを提供します。 このモジュールの微妙な違いと、それがどのようにヒープの力をもたらすかについて詳しく見てみましょう。
heapq
モジュールは個別のヒープ データ型を提供しません。 代わりに、通常の Python リストで動作し、リストを変換して次のように扱う関数を提供します。 バイナリヒープ.
このアプローチはメモリ効率が高く、Python の既存のデータ構造とシームレスに統合されます。
つまり、 ヒープはリストとして表現されます in heapq
。 この表現の美しさはそのシンプルさです。ゼロから始まるリスト インデックス システムは暗黙的なバイナリ ツリーとして機能します。 位置にある任意の要素に対して i
、 その:
- 左側の子が位置にあります
2*i + 1
- 右の子が位置にいます
2*i + 2
- 親ノードは の位置にあります
(i-1)//2
この暗黙的な構造により、個別のノードベースのバイナリ ツリー表現が不要になり、操作が簡単になり、メモリ使用量が最小限に抑えられます。
スペースの複雑さ: ヒープは通常、バイナリ ツリーとして実装されますが、子ノードの明示的なポインタを格納する必要はありません。 これにより、スペース効率が向上し、スペースの複雑さが軽減されます。 O(N) n 個の要素を格納します。
重要な注意点は、 heapq
モジュール デフォルトで最小ヒープを作成します。 これは、最小の要素が常にルート (またはリストの最初の位置) にあることを意味します。 最大ヒープが必要な場合は、要素に次の値を乗算して順序を反転する必要があります。 -1
またはカスタム比較関数を使用します。
Pythonの heapq
モジュールは、開発者がリストに対してさまざまなヒープ操作を実行できるようにする一連の関数を提供します。
注: 使用するには heapq
アプリケーション内のモジュールを使用するには、単純なメソッドを使用してインポートする必要があります。 import heapq
.
次のセクションでは、これらの基本的な操作をそれぞれ深く掘り下げ、その仕組みとユースケースを探っていきます。
リストをヒープに変換する方法
heapify()
function は、多くのヒープ関連タスクの開始点です。 これは反復可能 (通常はリスト) を受け取り、最小ヒープのプロパティを満たすようにその要素をその場で再配置します。
ベストプラクティス、業界で認められた標準、および含まれているチートシートを含む、Gitを学習するための実践的で実用的なガイドを確認してください。 グーグルGitコマンドを停止し、実際に 学ぶ それ!
import heapq data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
heapq.heapify(data)
print(data)
これにより、有効な最小ヒープを表す並べ替えられたリストが出力されます。
[1, 1, 2, 3, 3, 9, 4, 6, 5, 5, 5]
時間計算量: を使用して、順序なしリストをヒープに変換します。 heapify
関数は O(N) 手術。 これは直観に反するように思えるかもしれませんが、そうであると予想されるかもしれません。 O(nlogn)ですが、ツリー構造の特性により、線形時間で達成できます。
ヒープに要素を追加する方法
heappush()
関数を使用すると、ヒープのプロパティを維持しながら新しい要素をヒープに挿入できます。
import heapq heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 3)
heapq.heappush(heap, 7)
print(heap)
コードを実行すると、最小ヒープ プロパティを維持する要素のリストが表示されます。
[3, 5, 7]
時間計算量: ヒープへの挿入操作 (ヒープ プロパティを維持しながら新しい要素をヒープに配置する操作) の時間計算量は次のとおりです。 O(logn)。 これは、最悪の場合、要素がリーフからルートまで移動しなければならない可能性があるためです。
ヒープから最小の要素を削除して返す方法
heappop()
関数は、ヒープ (最小ヒープ内のルート) から最小の要素を抽出して返します。 削除後も、リストが有効なヒープのままであることが保証されます。
import heapq heap = [1, 3, 5, 7, 9]
print(heapq.heappop(heap))
print(heap)
注: heappop()
は、ヒープ ソート アルゴリズムなど、要素を昇順で処理する必要があるアルゴリズムや、タスクが緊急度に基づいて実行される優先キューを実装する場合に非常に役立ちます。
これにより、最小の要素と残りのリストが出力されます。
1
[3, 7, 5, 9]
ここでは、 1
からの最小要素です heap
、残りのリストは、削除した後でもヒープ プロパティを維持します。 1
.
時間計算量: ルート要素 (最小ヒープ内で最小のもの、または最大ヒープ内で最大のもの) を削除し、ヒープを再編成する場合にも時間がかかります。 O(logn) 時間。
新しいアイテムをプッシュして最小のアイテムをポップする方法
heappushpop()
関数は、新しい項目をヒープにプッシュし、次にヒープから最小の項目をポップして返す複合操作です。
import heapq heap = [3, 5, 7, 9]
print(heapq.heappushpop(heap, 4)) print(heap)
これは出力します 3
、最小の要素、新しい要素を出力します。 heap
現在含まれているリスト 4
ヒープのプロパティを維持しながら:
3
[4, 5, 7, 9]
注: 使い方 heappushpop()
この関数は、新しい要素をプッシュし、最小の要素をポップする操作を個別に実行するよりも効率的です。
最小のアイテムを置き換えて新しいアイテムをプッシュする方法
heapreplace()
関数は、最小の要素をポップし、新しい要素をヒープにプッシュします。これをすべて XNUMX 回の効率的な操作で実行します。
import heapq heap = [1, 5, 7, 9]
print(heapq.heapreplace(heap, 4))
print(heap)
これは印刷します 1
、最小の要素、リストには 4 が含まれ、ヒープ プロパティが維持されます。
1
[4, 5, 7, 9]
Note: heapreplace()
ローリング ウィンドウ操作やリアルタイム データ処理タスクなど、現在の最小要素を新しい値に置き換えるストリーミング シナリオで有益です。
Python のヒープ内で複数の極値を見つける
nlargest(n, iterable[, key])
および nsmallest(n, iterable[, key])
関数は、反復可能オブジェクトから複数の最大または最小の要素を取得するように設計されています。 少数の極値のみが必要な場合は、反復可能全体をソートするより効率的です。 たとえば、次のリストがあり、リスト内で XNUMX つの最小値と XNUMX つの最大値を見つけたいとします。
data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
ここでは、 nlargest()
および nsmallest()
関数は便利です:
import heapq data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
print(heapq.nlargest(3, data)) print(heapq.nsmallest(3, data))
これにより XNUMX つのリストが得られます。XNUMX つは XNUMX つの最大値を含み、もう XNUMX つは、 data
リスト:
[9, 6, 5]
[1, 1, 2]
カスタム ヒープを構築する方法
一方、パイソンは heapq
モジュールはヒープを操作するための強力なツールのセットを提供しますが、デフォルトの最小ヒープ動作では十分ではないシナリオがあります。 最大ヒープの実装を検討している場合でも、カスタム比較関数に基づいて動作するヒープが必要な場合でも、カスタム ヒープを構築することが解決策となる可能性があります。 特定のニーズに合わせてヒープを調整する方法を見てみましょう。
を使用して最大ヒープを実装する heapq
デフォルトでは、 heapq
作成します。 最小ヒープ。 ただし、簡単なトリックを使用すると、最大ヒープを実装することができます。 このアイデアは、要素に次の値を乗算して要素の順序を反転することです。 -1
ヒープに追加する前に:
import heapq class MaxHeap: def __init__(self): self.heap = [] def push(self, val): heapq.heappush(self.heap, -val) def pop(self): return -heapq.heappop(self.heap) def peek(self): return -self.heap[0]
このアプローチでは、(絶対値に関して) 最大の数が最小になり、 heapq
最大ヒープ構造を維持する機能。
カスタム比較関数を使用したヒープ
場合によっては、要素の自然な順序に基づいて比較するだけではないヒープが必要になることがあります。 たとえば、複雑なオブジェクトを扱っている場合、または特定の並べ替え基準がある場合、カスタム比較関数が不可欠になります。
これを実現するには、比較演算子をオーバーライドするヘルパー クラスで要素をラップします。
import heapq class CustomElement: def __init__(self, obj, comparator): self.obj = obj self.comparator = comparator def __lt__(self, other): return self.comparator(self.obj, other.obj) def custom_heappush(heap, obj, comparator=lambda x, y: x < y): heapq.heappush(heap, CustomElement(obj, comparator)) def custom_heappop(heap): return heapq.heappop(heap).obj
この設定を使用すると、任意のカスタム コンパレータ関数を定義し、それをヒープで使用できます。
まとめ
ヒープは多くの操作に対して予測可能なパフォーマンスを提供するため、優先度ベースのタスクにとって信頼できる選択肢となります。 ただし、当面のアプリケーションの特定の要件と特性を考慮することが重要です。 場合によっては、ヒープの実装を調整したり、代替のデータ構造を選択したりすることで、実際のパフォーマンスが向上する可能性があります。
これまで説明してきたように、ヒープは単なるデータ構造ではありません。 それらは、効率、構造、適応性の融合を表しています。 基本的なプロパティから Python での実装まで heapq
モジュール、ヒープは、無数の計算上の課題、特に優先順位を中心とした課題に対する堅牢なソリューションを提供します。
- SEO を活用したコンテンツと PR 配信。 今日増幅されます。
- PlatoData.Network 垂直生成 Ai。 自分自身に力を与えましょう。 こちらからアクセスしてください。
- プラトアイストリーム。 Web3 インテリジェンス。 知識増幅。 こちらからアクセスしてください。
- プラトンESG。 カーボン、 クリーンテック、 エネルギー、 環境、 太陽、 廃棄物管理。 こちらからアクセスしてください。
- プラトンヘルス。 バイオテクノロジーと臨床試験のインテリジェンス。 こちらからアクセスしてください。
- 情報源: https://stackabuse.com/guide-to-heaps-in-python/
- :持っている
- :は
- :not
- :どこ
- $UP
- 1
- 10
- 11
- 12
- 13
- 14
- 視聴者の38%が
- 20
- 7
- 8
- 9
- a
- 私たちについて
- 絶対の
- アクセス
- アクセス可能な
- 達成する
- 達成
- 実際に
- 加えます
- 追加されました
- 追加
- 利点
- 後
- 空気
- 空港
- 警告
- アルゴリズム
- アルゴリズム
- すべて
- 許す
- 許可
- ことができます
- また
- 代替案
- 常に
- an
- および
- 別の
- 回答
- どれか
- 離れて
- 申し込み
- アプローチ
- です
- 周りに
- 配列
- 記事
- AS
- 登ります
- At
- バランシング
- ベース
- ベース
- BE
- 美容
- なぜなら
- になる
- 行動
- 有益な
- より良いです
- 国境
- 両言語で
- 持って来る
- もたらす
- ビルド
- 建物
- 内蔵
- にぎやか
- 焙煎が極度に未発達や過発達のコーヒーにて、クロロゲン酸の味わいへの影響は強くなり、金属を思わせる味わいと乾いたマウスフィールを感じさせます。
- by
- 缶
- 場合
- 例
- カテゴリ
- 中心の
- 一定
- 課題
- 特性
- 子
- 子供達
- 選択
- class
- コード
- コーディング
- コレクション
- 組み合わせた
- 来ます
- コマンドと
- 比較します
- 比べ
- 比較
- コンプリート
- 複雑な
- 複雑さ
- 計算的
- コンセプト
- 結論
- 合流
- 検討
- 整合性のある
- 含まれています
- コントラスト
- 変換
- 基本
- 対応する
- カウンターパート
- 作成した
- 作成します。
- 基準
- 頂点
- 電流プローブ
- カスタム
- データ
- データ処理
- データ構造
- 取引
- 深いです
- より深い
- デフォルト
- 定義します
- 定義済みの
- 定義
- 掘り下げる
- によっては
- 設計
- 開発者
- 異なります
- 明確な
- 明らかに
- 優れました
- ダイビング
- ダイビング
- doesnの
- ドン
- 原因
- ダイナミック
- 各
- 効率
- 効率的な
- 効率良く
- どちら
- 素子
- 要素は
- 乗り出す
- enable
- 努力
- 確実に
- 確保する
- 全体
- 完全に
- 等しい
- 等しいです
- 特に
- 本質
- 本質的な
- さらに
- EVER
- あらゆる
- 例
- 除く
- 実行された
- 既存の
- 期待する
- 探る
- 探る
- 抽出
- 抽出物
- 極端な
- 両極端
- 目
- 要因
- 有名な
- 特徴
- 少数の
- フィボナッチ
- 埋め
- もう完成させ、ワークスペースに掲示しましたか?
- 名
- フィット
- 柔軟性
- 航空券
- フォーカス
- フォロー中
- 何よりも
- 形式でアーカイブしたプロジェクトを保存します.
- 前進
- 基礎的な
- 頻繁な
- 頻繁に
- から
- function
- 機能性
- 機能
- 基本的な
- Gitの
- 与える
- 与えられた
- 良い
- 統治
- 大きい
- 陸上
- ガイド
- ハンド
- 実践的な
- ハンディ
- 持ってる
- 持って
- 高さ
- 助けます
- 最高
- 保持している
- ホバー
- 認定条件
- How To
- しかしながら
- HTTPS
- ICON
- アイデア
- if
- 実装する
- 実装
- 実装
- 実装
- 実装
- import
- 重要性
- 重要
- in
- 含まれました
- 含ま
- 増える
- index
- 固有の
- を取得する必要がある者
- 統合する
- に
- 概要
- 貴重な
- IT
- ITS
- 自体
- 旅
- ただ
- キー
- 既知の
- 着陸
- 最大の
- 姓
- LEARN
- 学習
- 最低
- 左
- less
- う
- レベル
- LG
- ある
- ような
- リスト
- リスト
- ll
- ログ
- 探して
- 最低
- 製
- メイン
- 維持する
- 保守
- 維持
- make
- 作る
- 作成
- 管理します
- 操作
- 操作
- 多くの
- マックス
- 手段
- 力学
- メモリ
- マージ
- かもしれない
- 分
- 最小限の
- 最小
- 分
- ミラーリング
- モジュール
- 他には?
- もっと効率的
- 最も
- の試合に
- 掛け算
- 無数の
- ナチュラル
- 自然
- 必要
- 必要とされる
- ニーズ
- ネットワーク
- 新作
- いいえ
- ノード
- 注目すべき
- 今
- ニュアンス
- 数
- 番号
- オブジェクト
- of
- オフ
- 提供
- オファー
- on
- ONE
- の
- 〜に
- 動作
- 操作
- 業務執行統括
- 演算子
- 反対
- 最適化
- 最適化
- or
- 注文
- その他
- 私たちの
- でる
- 出力
- 自分の
- 特に
- ピーク
- 実行する
- パフォーマンス
- 実行
- 実行
- おそらく
- ピース
- 頂点
- 配置
- プラトン
- プラトンデータインテリジェンス
- プラトデータ
- ポイント
- ポップ
- ポップス
- 位置
- ポジショニング
- ポジション
- 潜在的な
- 電力
- 発電所
- 実用的
- 予測可能な
- 主要な
- 素数
- 原則
- 原則
- 印刷物
- プリント
- 優先順位をつける
- 優先順位
- プロセス
- 処理
- 進捗
- プロパティ
- 財産
- 提供します
- は、大阪で
- プッシュ
- プッシュ
- 押す
- Python
- クイック
- RE
- 読む
- 現実の世界
- への
- リアルタイムデータ
- レギュラー
- 信頼性のある
- 残り
- 残っている
- 除去
- 削除します
- 削除済み
- 除去
- 再編成
- replace
- 表す
- 表現
- で表さ
- 表し
- 必要とする
- 要件
- return
- 収益
- 富裕層
- 右
- リング
- 堅牢な
- 圧延
- ルート
- ルール
- ランニング
- s
- 言う
- シナリオ
- シームレス
- を検索
- セクション
- 思われる
- 自己
- 別
- シーケンス
- 仕える
- セッションに
- Shadow
- シート
- 簡単な拡張で
- 単純
- から
- 座っ
- 熟練した
- So
- 溶液
- 一部
- スペース
- 特定の
- 特に
- スピード
- スタックアバス
- 規格
- スタンド
- start
- 起動
- 開始
- Force Stop
- ストレージ利用料
- 保存
- 簡単な
- ストリーミング
- 構造の
- 構造
- 構造
- そのような
- スイート
- SVG
- テーラー
- 取り
- 取得
- タスク
- 条件
- より
- それ
- 世界
- アプリ環境に合わせて
- それら
- その後
- そこ。
- ボーマン
- 彼ら
- もの
- この
- それらの
- 三
- 介して
- 時間
- <font style="vertical-align: inherit;">回数</font>
- 〜へ
- 豊富なツール群
- top
- トラフィック
- 最適化の適用
- 変換
- 遷移
- 旅行
- 治療する
- 治療
- ツリー
- 樹木類
- true
- 微調整
- 2
- type
- 一般的に
- わかる
- ユニーク
- 緊急
- 緊急
- us
- 使用法
- つかいます
- 中古
- 有効な
- 値
- 価値観
- さまざまな
- Ve
- 視覚化する
- 欲しいです
- we
- この試験は
- いつ
- たびに
- かどうか
- which
- while
- 意志
- ウィンドウを使用して入力ファイルを追加します。
- 以内
- 無し
- 仕事
- ワーキング
- 世界
- 最悪
- ラップ
- X
- 産出
- You
- あなたの
- ゼファーネット