Min-max heap とは

コンピュータサイエンスでは、min-maxヒープは、min-heapとmax-heapの両方の有用性を組み合わせた完全なバイナリツリーデータ構造です。つまり、最小時間と最大時間の一定時間の検索と対数時間の削除を提供しますその中の要素。これにより、min-maxヒープは両端の優先順位キューを実装するための非常に有用なデータ構造になります。バイナリのmin-heapsやmax-heapsのように、min-maxヒープは対数の挿入と削除をサポートし、線形時間で構築することができます。最小最大ヒープは、しばしば暗黙的に配列内に表現されます。したがって、暗黙のデータ構造と呼ばれています。
最小最大ヒーププロパティは次のとおりです。ツリー内の偶数レベルの各ノードはその子孫のすべてよりも小さく、ツリー内の奇数レベルの各ノードはその子孫のすべてよりも大きい。
find-median、delete-median、find(k)(構造内のk番目の最小値の決定)、operation delete(k)(k番目のものを削除するなど、他の順序統計操作を効率的にサポートするように構造を一般化することもできます。構造の最小値)、kの任意の固定値(または値の集合)に対してこれらの最後の2つの演算は、それぞれ一定の時間および対数の時間で実施することができる。 min-max順序付けの概念は、左または右の木などの最大または最小順序に基づいて他の構造に拡張して、新しい(そしてより強力な)クラスのデータ構造を生成することができます。 min-maxヒープは、外部クイックソートを実装するときにも役立ちます。