こんにちは、この図について質問がありました。どのノードがルート ノードであるかをどのように判断できますか?また、このようなものをヒープ化するにはどうすればよいですか?
ありがとうございました。
編集:申し訳ありませんが、heapifyと言ったときは、最大ヒープを作成することを意味していました。通常、通常のヒープでは、葉ノードではない最初のノードから始めて、左から右に移動し、下にふるいにかけます。ここでそれを行う方法がわかりません。
これは二項ヒープであり、ルートは 1 つではなく、ルートのセットを持ちます (二項ヒープは二項ツリーのセットであるため)。
「最大ヒープを作成する」とはどういう意味ですか? 最大ヒープと二項ヒープは、Java と JavaScript のように互いに近いものです。
最小 n 回を抽出すると、最大ヒープであるソート済み配列を取得できます。複雑さは O(n*log(n)) です。
概念的には、ルートは祖先を持たない唯一のノードである必要があります。ダイアグラムの場合は1です。
二項ヒープを二項ヒープとして処理しようとしていると思いますが、これは機能しません。
バイナリヒープは、明示的なリンクなしで配列に格納できます。リンクは、配列内の位置に暗黙的に含まれます。順序付けされていない配列を「ヒープ化」して、O(n)時間で有効なバイナリヒープを作成するように並べ替えることができます。これがバイナリヒープの重要な利点です。メモリをうまく使用する軽量の実装があります。
私は二項ヒープを実装したことがなく、それらを研究しましたが、それは少し前のことです。ただし、二項ヒープは二項ヒープではなく、そのように実装することはできないと私はかなり確信しています。二項ヒープには独自の利点がありますが、二項ヒープのすべての利点を維持しているわけではありません。二項ヒープが普遍的に優れている場合、誰も二項ヒープを気にしません。
IIRC、(二項ヒープのベースとなる)二項ツリーの通常の実装では、各親ノードの子のリンクリストとルートのリンクリストがあります。これらのリンクリストは明示的なリンクを使用します。これは、ノードごとにk個の子をサポートする方法であり、kに上限はありません。
バイナリヒープの重要な追加操作はマージです。二項ヒープが暗黙的なリンクを持つ配列に格納されている場合、マージには明らかに多くのコピーが必要になります。つまり、最初に1つの配列から別の配列にアイテムをコピーします。したがって、効率的なマージは不可能です。二項ヒープの主な利点は失われます。
ただし、明示的なリンクを使用すると、2つの二項ツリーを1つに結合することは、O(1)ポインターをいじる操作(リンクリストの先頭に項目を追加する)であるため、2つの二項ヒープをO(log n)二項ツリーとマージできます。非常に効率的にマージします。
これは、並べ替えられた配列と二分探索木の違いに少し似ています。確かに、ソートされた配列には利点がありますが、制限もあります。配列内でアイテムを移動せずにリンクを1つまたは2つ変更するだけの場合、一部の操作はより効率的です。これらの操作が不要な場合もあります。リンクの必要性を回避し、並べ替えられた配列をバイナリ検索する方が効率的です。これは、暗黙的なリンクを使用して完全にバランスの取れたバイナリ検索ツリーを検索するのと同じです。