基本的に、引用されたステートメントは、ヒープへのデータ要素の挿入およびヒープからの削除の場所を解決する問題を指します。バイナリ ヒープの「形状プロパティ」を維持するには、ヒープの最下位レベルを常に左から右に埋めて、空のノードを残さないようにする必要があります。バイナリ ヒープの平均 O(1) 挿入および削除時間を維持するには、次の挿入の場所と、ルート ノードの削除に使用する最下位レベルの最後のノードの場所を特定できる必要があります。一定時間で。
配列に格納されたバイナリ ヒープ (ウィキペディアのエントリで説明されているように、暗黙的で圧縮されたデータ構造を持つ) の場合、これは簡単です。配列の最後に最新のデータ メンバーを挿入し、それを所定の位置に "バブル" します (ヒープ ルールに従います)。または、ルートを配列の最後の要素に置き換えて、削除のために「バブリングダウン」します。配列ストレージのヒープの場合、ヒープ内の要素の数は、次のデータ要素が挿入される場所と、削除に使用する最後の要素を見つける場所への暗黙的なポインターです。
ツリー構造に格納されたバイナリ ヒープの場合、この情報は明らかではありませんが、完全なバイナリ ツリーであるため、計算することができます。たとえば、4 つの要素を持つ完全なバイナリ ツリーでは、挿入ポイントは常にルート ノードの左の子の右の子になります。削除に使用するノードは、常にルート ノードの左の子の左の子になります。また、特定の任意のツリー サイズに対して、ツリーは常に明確に定義された挿入ポイントと削除ポイントを持つ特定の形状を持ちます。ツリーは任意のサイズの特定の構造を持つ「完全なバイナリ ツリー」であるため、O(1) 時間で挿入/削除の場所を計算することが非常に可能です。ただし、問題は、ノードが構造的にどこにあるかを知っていても、ノードがメモリ内のどこにあるかがわからないことです。そう、O(log n) プロセスである特定のノードに到達するには、ツリーをトラバースする必要があります。これは、すべての挿入と削除を最小の O(log n) にし、通常望ましい O(1) 動作を破ります。すべての検索 (「深さ優先」またはその他の検索) は、トラバーサルの問題が指摘されているため、少なくとも O(log n) になり、半ソートされたヒープのランダムな性質のために、通常は O(n) になります。
秘訣は、データ構造を拡張する (ウィキペディアの記事で言及されているように、ツリーを「スレッド化」する) か、追加のポインターを使用することによって、これらの挿入/削除ポイントを一定時間内に計算および参照できるようにすることです。
少ないメモリと追加のコーディング オーバーヘッドで、最も理解しやすいと思われる実装は、通常の単純なバイナリ ツリー構造を使用することです ([data, pParent, pLeftChild, pRightChild] として定義された pRoot と Node を使用)。 2 つのポインター (pInsert と pLastNode) を追加します。pInsert と pLastNode は両方とも、挿入サブルーチンと削除サブルーチン中に更新され、構造内のデータが変更されたときにそれらを最新の状態に保ちます。この実装は、挿入ポイントと構造の最後のノードの両方に O(1) アクセスを提供し、挿入と削除の両方で全体的な O(1) 動作を維持できるようにする必要があります。実装のコストは、2 つの追加ポインターと、挿入/削除サブルーチンでのマイナーな追加コードです (別名、最小)。
EDIT : O(1) insert() の疑似コードを追加
以下は、平均して O(1) である挿入サブルーチンの擬似コードです。
define Node = [T data, *pParent, *pLeft, *pRight]
void insert(T data)
{
do_insertion( data ); // do insertion, update count of data items in tree
# assume: pInsert points node location of the tree that where insertion just took place
# (aka, either shuffle only data during the insertion or keep pInsert updated during the bubble process)
int N = this->CountOfDataItems + 1; # note: CountOfDataItems will always be > 0 (and pRoot != null) after an insertion
p = new Node( <null>, null, null, null); // new empty node for the next insertion
# update pInsert (three cases to handle)
if ( int(log2(N)) == log2(N) )
{# #1 - N is an exact power of two
# O(log2(N))
# tree is currently a full complete binary tree ("perfect")
# ... must start a new lower level
# traverse from pRoot down tree thru each pLeft until empty pLeft is found for insertion
pInsert = pRoot;
while (pInsert->pLeft != null) { pInsert = pInsert->pLeft; } # log2(N) iterations
p->pParent = pInsert;
pInsert->pLeft = p;
}
else if ( isEven(N) )
{# #2 - N is even (and NOT a power of 2)
# O(1)
p->pParent = pInsert->pParent;
pInsert->pParent->pRight = p;
}
else
{# #3 - N is odd
# O(1)
p->pParent = pInsert->pParent->pParent->pRight;
pInsert->pParent->pParent->pRight->pLeft = p;
}
pInsert = p;
// update pLastNode
// ... [similar process]
}
したがって、insert(T) は平均で O(1) です。O(log N) のときにツリーを 1 レベル増やす必要がある場合を除いて、すべての場合で正確に O(1) です。削除）。別のポインター (pLeftmostLeaf) を追加すると、insert() がすべてのケースで O(1) になり、完全なバイナリ ツリーで挿入と削除が交互に繰り返されるという病的なケースを回避できます。(pLeftmost の追加は演習として残します [かなり簡単です]。)