考虑下面的问题，我不是我目前的解决方案完全确定：
题 ：
给定的最大堆与n元件，其被存储在数组中A ，是有可能打印的所有最大K中的元素O(K*log(K))
我的回答 ：
是的，是的，因为搜索的元素需要O(log(K))因此这样做
对于K元素将采取O(K * log(K))的运行时间。
Answer 1:
这是可能的最大堆，因为你是从树上唯一的印刷元素，不提取它们。
通过识别最大元件，其位于所述根节点开始。 形成一个指向一个节点，并把它添加到人少的“最大值”列表中。 然后，对于每个所述的k值，执行在一个循环中执行以下步骤。
- 从列表中弹出的最大元素，以O（1）。
- 打印其价值，以O（1）。
- 每次插入这个最大元素到列表中的孩子。 保持排序，当你将其插入，以O时间（日志列表）（尺寸）。 这份名单的最大尺寸，因为我们执行这个循环k次，是分支尺寸* K。 因此，该步骤花费O（日志（k））的时间。
总体上，然后，运行时间为O（KLOG（k））的，根据需要。
Answer 2:
搜索在大小为N的堆中的元素不是O（K）。 首先，它没有任何意义，对于寻找一个元素的时间复杂度取决于你正在试图提取（这是K表示）元素的数量。 此外，还有在堆搜索没有这样的事情 - 除非你在O（N）的标准外观-AT-每一个元素搜索。
然而，在堆中找到最大的元素是O（1）设计（我明显地假设，这是一个最大堆，所以最大因素是在堆的顶部），然后从一堆去除最大的元素大小N为O（日志（N））（与叶元件替换它，并具有叶渗透背下来的堆）。
所以，从一个堆提取K个元素， 并返回非提取的元素的堆 ，将采取O（K·日志（N））的时间。
如果你从堆中提取K个元素非破坏性的 ，会发生什么？ 您可以通过保持堆的-堆（其中一个堆的价值是其最大元素的值）做到这一点。 最初，这个堆的-堆仅包含一个元素（原堆）。 要提取的下一个最大元素，则提取该顶部堆，提取其顶部元件（它是最大值），然后重新插入两个子堆返回到堆的-堆。
这由一个生长在每一个去除（删除一个，添加两个），这意味着它不会比K中的元素持有更多的堆的-堆，所以删除一加二将采取O（日志（K） ）。 迭代这个，你会得到一个实际的O（K·日志（K））的算法，做返回前K元素，但不能返回的非抽出元素的堆。
Answer 3:
我发现其他答案混淆，所以我决定用一个实际的例子堆来解释它。 假设原来的堆大小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：添加指针节点10
10'
New Heap, size = 1, root = 10', root->left = 5, root right->3
打印1最集中的元素= 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堆删除根节点。 （与最右边的离开，删除根节点和气泡向下当前根维持堆属性交换节点最多）
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：来自新的堆删除根节点。 （交换节点最多（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
打印第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）的
希望这可以帮助！
不久慈龙，
多伦多大学。
Answer 4:
事实上，这是太容易，在提取最大元素是O(log(N))其中N是堆的大小。 和N≠K 。
我补充一点，寻找一个随机元素是O(N)而不是O(Log(N))但在这种情况下，我们要提取的最大。
Answer 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.
文章来源: Print the biggest K elements in a given heap in O(K*log(K))?
