logo标签列表

如何以O(K*log(K))的时间复杂度打印出给定堆中最大的K个元素？

algorithmsearchtreeheapbig-o
16

针对以下问题，我对当前的解决方案并不完全确定：

问题：

给定一个最大堆，有 n 个元素，存储在数组 A 中，是否可以用 O(K*log(K)) 的时间复杂度打印出最大的 K 个元素？

我的答案：

可以，因为查找一个元素需要 O(log(K)) 的时间，因此对于 K 个元素这样做将需要 O(K * log(K)) 的运行时间。

1
可能重复了从二叉堆中查找第k小元素的O(klogk)时间算法。也许不是重复，因为链接的问题要求第k个元素而不是第k大的元素列表，但是思路是相同的。 - amit
5个回答
20
在大小为N的堆中搜索元素不是O(K)。首先，找到一个元素的时间复杂度取决于您尝试提取的元素数量（即K）是没有意义的。其次，在堆中查找没有这样的事情，除非您将标准的遍历所有元素的搜索算法计算在O(N)内。
然而，根据设计，在堆中找到最大的元素是O(1)的（我显然假设它是一个最大堆，因此最大的元素在堆的顶部），从大小为N的堆中删除最大的元素是O(log(N))的（用一个叶子元素替换它，并使该叶子元素重新下移至堆中）。
因此，从堆中提取K个元素，并返回未被提取元素的堆，需要O(K·log(N))的时间。
如果您从堆中以非破坏性方式提取K个元素会发生什么？ 您可以通过保留堆的堆（其中堆的值是其最大元素的值）来执行此操作。最初，这个堆-of-堆只包含一个元素（原始堆）。要提取下一个最大元素，您提取顶部堆，提取其顶部元素（即最大元素），然后将两个子堆重新插入堆-of-堆中。
每次删除（删除一个，添加两个）都会使堆-of-堆增长一个，这意味着它永远不会容纳超过K个元素，并且删除一个添加两个将花费O(log(K))的时间。 反复进行此操作，您就可以获得实际的O(K·log(K))算法，该算法返回前K个元素，但无法返回未提取元素的堆。
请注意，我已经更新了问题 - 堆确实是最大堆，但它是以数组的形式给出的。 - JAN
1
它是一个数组这个事实并不改变任何事情。 - Victor Nicollet
数组是堆的存储策略，但无论如何存储，堆仍然是一棵树。当你从堆中移除顶部元素时，你会得到两个子堆，它们之前是该元素的两个子节点。在数组情况下，这两个子堆恰好存储在与原始堆相同的数组中，但这只是一个偶然事件 - 探索它们的规则仍然保持不变。 - Victor Nicollet
1
有人能解释一下“返回未提取元素的堆”和“从堆中破坏性地提取K个元素”的区别吗？ - prashantitis
@Prashant 应该是非破坏性的。 - Eric Z
这非常聪明。 - Francesco Dondi
15

我发现其他答案很令人困惑，所以我决定用一个实际的堆例子来解释。假设原始堆的大小为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

第二步c: 从新堆中删除根节点。(将最大节点与最右侧的叶子节点交换，删除根节点并将当前根节点向下移动以维护堆属性)
  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

第三步c：从新堆中删除根节点。 (将新堆的最大节点（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

打印第三大的元素 = 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

打印第四大的元素 = 3

步骤5a：从原堆中查找新堆的根节点左子节点。在新堆中添加指向左子节点（在此例中为2'）的指针。

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

步骤5b：从原堆中查找新堆的根节点的右子节点。将左子节点（在此例中为0'）添加到新堆中，并保留HTML标签。
     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

打印第五大的元素 = 2

最后，因为我们已经进行了k次迭代，所以k = 5。现在，我们可以从新堆中提取根元素的值。在这种情况下，该值为2。 因此，我们已经找到了原始堆中第k大的值。

时间复杂度T（N，k）= O（klogk） 空间复杂度S（N，k）= O（k）

希望这有所帮助！

祝好， Soon Chee Loong, 多伦多大学。

在步骤3c和5c中，您说要将最大节点与最右侧的叶子交换，但您却将其与最左侧的叶子交换了？ - user881300
@user881300 原始堆中最右侧的叶子节点。谢谢，我会在解释中澄清。 - Chee Loong Soon
11

在最大堆中，这是可能的，因为您只是从树中打印元素，而不是提取它们。

首先要找到位于根节点的最大元素。形成一个指向节点的指针，并将其添加到另外一个空的“最大值”列表中。然后，对于每个k值，在循环中执行以下步骤。

  • 从列表中弹出最大的元素，需要 O(1) 的时间。
  • 打印其值，需要 O(1) 的时间。
  • 将该最大元素的每个子节点插入到列表中。在插入时保持排序，需要 O(log(列表大小)) 的时间。由于我们正在执行此循环 k 次，因此此列表的最大大小是分支大小*k。因此该步骤需要 O(log(k)) 的时间。

因此，总运行时间为 O(klog(k)), 正如所期望的一样。

1
第三步是否可以在O(log(k))时间内完成？如果数据结构是链表，则二分查找不可能（至少不能在log(k)时间内完成）？如果数据结构是数组，则插入不会是O(1)。如果我漏掉了什么，请纠正我。 - Shubham Goyal
我觉得最好先将元素复制到一个数组中，然后再对数组进行排序。 - Shubham Goyal
1
@ShubhamGoyal 数据结构本身可以是一个堆，支持O(log k)的插入和删除最大值。同意回答中关于操作复杂度的个别声明是不可能实现的。 - Niklas B.
5
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.
它是在@Victor Nicollet的答案中描述的相同算法。 - jfs
3

确实，提取最大元素太容易了，其时间复杂度为O(log(N))，其中N是堆的大小，且N≠K。

我想补充一点，在堆中搜索随机元素的时间复杂度为O(N)而不是O(Log(N))，但是在这种情况下我们需要提取最大值。

@ron 我的回答仍然有效。 - Thomash
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接