[解決済み] ヒープ化 VS ビルドヒープ

質問

私が学んでいるソースは、heapifyが（ゼロから）配列からヒープを構築すると言っている 'heapify'という概念の意味を確認してください。

いくつかの資料をググった結果、このように理解しました。

ヒーピファイが。

• ヒープのトップノードをポップし、最後のノードをトップに移動した後、ツリーをトップからボトムに並べ替え、再びヒープにします（ヒープ化します）。
• ヒープフィの時間計算量 O(log n)

Heapifyは、そうではありません。

• 配列からヒープを生成する。これはボトムアップ操作であり、時間計算量は O(n) である。

これでいいのでしょうか？

どのように解決するのですか？

基本的には heapify は、ルートノードがヒーププロパティに違反した場合に、ヒープを再アレンジするために使われるアルゴリズムです ( 子サブツリーはヒープでなければならない! ). ヒープを構築する上で、トップノードを挿入したり、ヒープから削除したりと、重要な役割を担っているのです。

Heapifyは。

• ヒープのトップノードをポップし、最後のノードをトップに移動した後、ツリーをトップからボトムに並べ替え、再びヒープにします（ヒープ化します）。
• ヒープフィの時間計算量 O(log n)

ここでは、どのように heapify は、先頭の要素が削除された場合に使用されます。最大/最小要素を一番上に維持する必要があるので、これは有効なケースです（それが最大ヒープか最小ヒープかによって異なります）。

Heapifyはそうではありません。

配列からヒープを生成するのは、時間計算量 O(n) のボトムアップ操作です。

おっしゃるとおり、そうではありません。先ほども言ったように heapify は、ヒープに対して操作を行った後、ヒープのプロパティを維持するための手段に過ぎません。

を使用します。 heapify を使用してヒープを構築し、結果として得られるデータ構造がヒープの要件を満たしていることを確認します。例えば、配列からminヒープを構築する必要があるとすると、以下のように行うことができる。

def min_heapify(arr, index):
    size      = len(arr)
    new_index = index
    left      = index * 2 + 1
    right     = index * 2 + 2

    if (left < size and arr[left] < arr[new_index]):
        new_index = left

    if (right < size and arr[right] < arr[new_index]):
        new_index = right

    if (new_index != index):
        arr[index], arr[new_index] = arr[new_index], arr[index]
        min_heapify(arr, new_index)

array = [5, 4, 3, 2, 1]

size = len(array)
for i in range((size//2) - 1, -1, -1):
    min_heapify(array, i)

print (array)

[1, 2, 3, 5, 4]

ご覧のように、たとえ heapify はヒープを構築するために積極的に使われますが、ヒープを構築することが heapify . あくまでも、必要不可欠なものなのです。