在O(K*log(K))中打印给定堆中最大的K元素？

Question

鉴于以下问题,我不能完全确定我目前的解决方案:

题 :

给定n存储在数组中的元素的最大堆A,是否可以打印所有最大的K元素O(K*log(K))？

我的回答:

是的,因为搜索元素需要O(log(K)),因此这样做

为K元素将需要 O(K * log(K))运行时间.

Answer 1

在大小为N的堆中搜索元素不是O(K).首先,找到一个元素的时间复杂度取决于您尝试提取的元素数量(这是K代表的)是没有意义的.此外,没有在堆中搜索的东西 - 除非你在O(N)中计算标准的每元素搜索量.

但是,找到堆中最大的元素是O(1)设计(我显然假设它是一个最大堆,所以最大元素位于堆的顶部),并从堆中删除最大元素大小N是O(log(N))(用叶子元素替换它,并让那片叶子在堆中向下渗透).

因此,从堆中提取K个元素并返回未提取元素的堆,将花费O(K·log(N))时间.

如果从堆中非破坏性地提取K个元素会发生什么？您可以通过保持堆堆(堆的值是其最大元素的值)来实现此目的.最初,这个堆堆只包含一个元素(原始堆).要提取下一个最大元素,请提取顶部堆,提取其顶部元素(这是最大值),然后将两个子堆重新插入堆堆中.

这会在每次删除时增加一堆堆(删除一个,添加两个),这意味着它永远不会超过K个元素,因此remove-one-add-two将采用O(log(K) ).迭代这个,你得到一个实际的O(K·log(K))算法确实返回了前K个元素,但是无法返回未提取元素的堆.

Answer 2

这在max-heap中是可能的,因为您只打印树中的元素,而不是提取它们.

首先确定位于根节点的最大元素.形成指向节点的指针,并将其添加到其他空的"maximums"列表中.然后,对于每个k值,请在循环中执行以下步骤.

• 弹出列表中的最大元素,取O(1).
• 打印其值,取O(1).
• 将此最大元素的每个子元素插入到列表中.插入时保持排序,取O(log(列表大小))时间.这个列表的最大大小,因为我们执行这个循环k次,是分支大小*k.因此,此步骤需要O(log(k))时间.

总的来说,根据需要,运行时间是O(klog(k)).

Answer 3

我发现其他答案令人困惑,所以我决定用一个实际的例子堆解释它.假设原始堆的大小为N,并且您希望找到第k个最大元素,此解决方案需要O(klogk)时间和O(k)空间.

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

想找到第五大元素.k = 5注意:在新堆中,您需要将指针存储到原始堆.这意味着,您不会删除或更改原始堆.原始堆是只读的.因此,您永远不必执行任何需要O(logN)时间的操作.

设x'是原始堆中值x的指针.

第一次迭代:将根节点的指针放入新堆中

步骤1:添加指向节点10的指针

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

打印第一大元素= 10

第二次迭代:参考原始堆并将其子项插入新堆中.(存储指向它们的指针而不是值本身).您希望存储指针的原因是,您可以稍后在原始堆中从O(1)访问它们以搜索其子项而不是O(N)来搜索该值在原始堆中的位置.

步骤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:从New Heap中删除根节点.(交换最右边的最大节点,删除根节点并向下冒泡当前根以保持堆属性)

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

打印第二大元素= 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:从New Heap中删除根节点.(交换New Heap的最大节点(5'),其最右边离开New Heap的原始堆(1'),删除根节点并向下冒泡当前root以保持堆属性)

    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:从New Heap中删除根节点.(交换最右边节点的最大节点,删除根节点并向下冒泡当前根以维护New Heap中的堆属性)

    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:从New Heap中删除根节点.(交换最大节点(3'),其最右边离开New Heap中的原始堆(为0'),删除根节点并向下冒泡当前根以保持New Heap中的堆属性)

     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

打印第五大元素= 2

最后,由于我们经历了k次迭代,k = 5.我们现在可以从新堆中提取根元素的值.在这种情况下,值为2.因此,我们找到了原始堆中的第k个最大值.

时间复杂度,T(N,k)= O(klogk)空间复杂度,S(N,k)= O(k)

希望这可以帮助!

很快Chee Loong,

多伦多大学.

Answer 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.