デザインコンテクストのLDデータ構造:Heapプロパティ — Heapsを強力なものにするシンプルなルール

「すべてがソートされているため、Heapは役に立ちません。 親が1つの簡単なルールに従うので、それは便利です。 以前の記事では、Heapが継続的な意思決定のために構築されていることを学びました。 最寄りのドライバーを割り当てるかどうか、次のプロセスをスケジュールするか、最も緊急サポートチケットを選択するか、システムは常に一つのことを必要とします。 しかし、それは興味深い質問を上げます。 Heapは、すべてのものをソートせずに常に最良の候補を知ることができますか? 答えは1つの簡単なルールにある:Heapプロパティ。 この単一のルールは、ヒープの力を与えるものです。 Heapsについて最大の誤解 多くの初心者は、このようなHeapを想像しています。 すべてが完全にソートされています。 論理的な感じです。 最大の要素が常に最初に来るべきならば、すべての要素が順番に配置されるべきではありませんか? 絶対に、いいえ。 ヒープは、より小さな問題が解決します。 最高の要素が常に到達するのは簡単です。 他のすべては、単純な関係に従う必要があります。 会社の階層を想像してみてください 会社の構造について考える。 役員は、社員一人ひとりに直接管理しません。 代わりに、各管理者は、そのすぐ下にある人々に対してのみ責任を負います。 すべての管理者が現地の責任を果たすため、組織全体が機能します。 ヒープはよく似ています。 すべてのノードは、即時の子供と正しい関係を維持する必要があります。 構造内の他のすべてのノードについて知る必要はありません。 Heap プロパティで Max Heap を見てみましょう。 パターンに注意してください。 すべての親は、その子供に相当する価値があります。 それはHeapプロパティです。 です。 すべてのノードがヒープ内の他のすべてのノードよりも大きくなければならないというルールはありません。 親子関係の問題だけ。 ミンヒープとは? 一部のシステムでは、最小値が優先されます。 例えば: 早い期限 最低応答時間 最も安い船積みの選択 この場合、ルールは単に逆転する。 例:再び、構造全体がソートされていない。 お問い合わせ