15

次の問題を考えると、現在の解決策には完全には確信が持てません:

質問 ：

n配列に格納されている要素の最大ヒープを指定すると、最大の要素をAすべて出力できますか?KO(K*log(K))

私の答え：

はい、そうです。要素の検索には が必要なO(log(K))ので、それを実行します。

forK要素は O(K * log(K))実行に時間がかかります。

4

5 に答える 5

17

Searching for an element in a heap of size N is not O(K). First, it does not make sense that the time complexity for finding one element depends on the number of elements you are trying to extract (which is what K represents). Also, there is no such thing as searching in a heap — unless you count the standard look-at-every-element search in O(N).

However, finding the largest element in a heap is O(1) by design (I am obviously assuming that it's a max-heap, so the maximum element is at the top of the heap), and removing the largest element from a heap of size N is O(log(N)) (replace it with a leaf element, and have that leaf percolate back down the heap).

So, extracting K elements from a heap, and returning the heap of non-extracted elements, would take O(K·log(N)) time.

What happens if you extract K elements non-destructively from the heap ? You can do this by keeping a heap-of-heaps (where the value of a heap is the value of its maximum element). Initially, this heap-of-heaps contains only one element (the original heap). To extract the next maximum element, you extract the top heap, extract its top element (which is the maximum) and then reinsert the two sub-heaps back into the heap-of-heaps.

This grows the heap-of-heaps by one on every removal (remove one, add two), which means it will never hold more than K elements, and so the remove-one-add-two will take O(log(K)). Iterate this, and you get an actual O(K·log(K)) algorithm that does returns the top K elements, but is unable to return the heap of non-extracted elements.

于 2012-06-26T14:36:24.437 に答える
11

これは、ツリーから要素を抽出するのではなく、要素を出力するだけであるため、最大ヒープで可能です。

ルート ノードにある最大要素を特定することから始めます。ノードへのポインタを作成し、空の「最大値」リストに追加します。次に、値ごとにk、次の手順をループで実行します。

  • O(1) を取って、リストから最大の要素を取り出します。
  • O(1) を取って、その値を出力します。
  • この最大要素の各子をリストに挿入します。それらを挿入するときにソートを維持し、O(log(リストのサイズ)) 時間かかります。このループを k 回実行するため、このリストの最大サイズは branch-size*k です。したがって、このステップには O(log(k)) 時間がかかります。

したがって、実行時間は、必要に応じて O(klog(k)) になります。

于 2012-06-26T15:38:28.407 に答える
11

他の答えがわかりにくいので、実際のヒープの例で説明することにしました。元のヒープのサイズが N で、k 番目に大きい要素を見つけたいとします。このソリューションには、O(klogk) 時間と O(k) スペースが必要です。

    10 
   /  \
  5    3 
 / \   /\
4   1 2  0
Original Heap, N = 7

5 番目に大きい要素を見つけたい。k = 5 注: 新しいヒープには、元のヒープへのポインターを格納する必要があります。これは、元のヒープを削除または変更しないことを意味します。元のヒープは読み取り専用です。したがって、O(logN) 時間を必要とする操作を行う必要はありません。

x' を元のヒープ内の値 x へのポインターとします。

1 回目の反復: ルート ノードのポインターを新しいヒープに取得する

ステップ 1: ノード 10 へのポインターを追加する

 10'
 New Heap, size = 1, root = 10', root->left = 5, root right->3

1 番目に大きい要素を出力 = 10

2 回目の反復: 元のヒープを参照し、両方の子を新しいヒープに挿入します。（値自体ではなく、それらへのポインターを保存します）。ポインターを格納する理由は、O(N) の代わりに元のヒープから O(1) にアクセスして、その値が元のヒープのどこにあるかを検索する代わりに、その子を検索できるようにするためです。

ステップ 2a: 元のヒープから新しいヒープのルート ノードの左の子を探します。左の子 (この場合は 5') のポインターを新しいヒープに追加します。

  10' 
 /
5'
New Heap, size = 2, root = 10', root->left = 5, root right->3

ステップ 2b: 元のヒープから新しいヒープのルート ノードの右の子を探します。左の子 (この場合は 3') のポインターを新しいヒープに追加します。 

  10' 
 / \
5'  3'
New Heap, size = 3, root = 10', root->left = 5, root right->3

ステップ 2c: 新しいヒープからルート ノードを削除します。(最大ノードを右端のリーブと交換し、ルート ノードを削除し、現在のルートをバブル ダウンしてヒープ プロパティを維持します)

  10'   swap    3'  remove & bubble   5'    
 / \     =>    / \       =>          /
5'  3'        5'  10'               3'
New Heap, size = 2, root = 5', root->left = 4, root right->1

2 番目に大きい要素を出力 = 5

ステップ 3a: 元のヒープから新しいヒープのルート ノードの左の子を探します。左の子 (この場合は 4') のポインターを新しいヒープに追加します。

  5'
 / \
3'  4'
New Heap, size = 3, root = 5', root->left = 4, root right->1

ステップ 3b: 元のヒープから新しいヒープのルート ノードの右の子を探します。左の子 (この場合は 1') のポインターを新しいヒープに追加します。 

    5'
   / \
  3'  4'
 /
1'
New Heap, size = 4, root = 5', root->left = 4, root right->1

ステップ 3c: 新しいヒープからルート ノードを削除します。(新しいヒープの最大ノード (5') を新しいヒープの元のヒープ (1') の右端と交換し、ルート ノードを削除し、現在のルートをバブル ダウンしてヒープ プロパティを維持します)

    5'        Swap     1' remove & bubble     4'
   / \         =>     / \       =>           / \
  3'  4'            3'   4'                 3'  1'
 /                 / 
1'                5'
New Heap, size = 3, root = 4', root->left = NULL, root right->NULL

3 番目に大きい要素を出力 = 4

この場合、ルートノードには元のヒープからの子がないため、ステップ 4a とステップ 4b は何もしません。

ステップ 4c: 新しいヒープからルート ノードを削除します。(最大ノードを右端と交換し、ルート ノードを削除し、現在のルートをバブルダウンして、新しいヒープのヒープ プロパティを維持します)

    4'        Swap     1' remove & bubble     3'
   / \         =>     / \       =>           / 
  3'  1'            3'   4'                 1'  
New Heap, size = 2, root = 3', root->left = 2, root right->0

4 番目に大きい要素を出力 = 3

ステップ 5a: 元のヒープから新しいヒープのルート ノードの左の子を探します。左の子 (この場合は 2') のポインターを新しいヒープに追加します。

     3'
    / \
   1'  2'
New Heap, size = 3, root = 3', root->left = 2, root right->0

ステップ 5b: 元のヒープから新しいヒープのルート ノードの右の子を探します。左の子 (この場合は 0') のポインターを新しいヒープに追加します。

     3'
    / \
   1'  2'
  /
 0'
New Heap, size = 4, root = 3', root->left = 2, root right->0

ステップ 5c: 新しいヒープからルート ノードを削除します。(最大ノード (3') を新しいヒープ内の元のヒープ (0') からの右端と交換し、ルート ノードを削除し、現在のルートをバブルダウンして、新しいヒープ内のヒープ プロパティを維持します)

     3'    Swap        0'  Remove & Bubble      2'
    / \     =>        / \         =>           / \
   1'  2'            1'  2'                   1'  0'
  /                 /
 0'                3'
New Heap, size = 3, root = 2', root->left = NULL, root->right = NULL

5 番目に大きい要素を出力 = 2

最後に、k 回の反復を行ったので、k = 5 です。これで、新しいヒープからルート要素の値を抽出できます。この場合、値は 2 です。したがって、元のヒープから k 番目に大きい値を見つけました。

時間の複雑さ、T(N,k) = O(klogk) 空間の複雑さ、S(N,k) = O(k)

お役に立てれば！

スン・チーロン、

トロント大学。

于 2015-09-14T06:49:22.250 に答える
4 
It is a simple and elegant algorithm to get first k elements of a max heap in k log(k) time.

steps:-

1.construct another max heap name it auxiliary heap
2.add root element of main heap to auxiliary heap
3.pop out the element from auxiliary heap and add it's 2 children to the heap
4.do step 2 and 3 till k elements have been popped out from auxiliary heap. Add the popped element's children to the auxiliary heap.
于 2013-06-30T12:47:13.540 に答える
3

確かに、それは簡単すぎます。最大要素を抽出するのO(log(N))はN、ヒープのサイズです。およびN≠K。

ランダム要素の検索はそうではO(N)ないことを追加しますO(Log(N))が、この場合、最大値を抽出します。

于 2012-06-26T14:31:38.730 に答える