以klog(k)复杂度打印最大堆大小n中的k个最大元素

Question

我试着写一个算法，打印最大堆的k个最大元素，但我不能以合适的复杂度来完成。

这是我写的伪代码-

Print_k_largest(A[1,…,n],k):
If k>Heapsize(A):Error
i=1
insert[B,A[i])
print(B[1])
k-=1
While k>0:
if 2*i< Heapsize(A):
Insert(B,A[2*i])
Insert(B,A[2*i+1])
elif 2*i= Heapsize(A):
Insert(B,A[2*i])
B[1]=B[Heapsize(B)]
Heapsize(B)-=1
Max-Heapify(B,1)
print(B[1])
i=Binary_search(A[1,…,n],B[1])      
k-=1

在此处输入图像描述

在这个解决方案中，我在原来的最大堆的基础上创建了一个新的最大堆，这样它的大小总是小于K，因此最大堆和其他这样的函数的复杂性是O(klogk)，而不是O(klogN)。此伪代码基于此处建议的解决方案。

这个想法是这样的-因为它是一个最大堆，最大的元素是根，第二大元素是根的一个子，第三个元素要么是另一个子，要么是当前最大元素的子，以此类推。在每次迭代中，我插入前一个最大元素(我之前打印的那个)的子，最大堆(使堆再次成为最大堆，因此根是最新最大的)并打印最新最大(最新根)。这个出色的解决方案的原理(当然不是我的，哈哈)是在第二个大小总是小于K的堆上进行所有更改(因为在K次迭代中，我们最多添加2个新元素并删除一个)，这样像max-heapify这样的操作的运行时间是O(logk)，而不是O(logn)。问题是，要添加当前最大的子，我需要访问它在原始树上的位置(索引)！我不知道如果不花logn和运行所有东西，该怎么做。

我很感激任何帮助。

Answer 1

所以我会创建第二个堆，但它不仅仅是一堆值——它将是原始堆中位置的堆，由该位置的值插入。

调用原始堆A和新堆B。首先将A的头部插入B。然后，反复弹出B的头部，并将儿童(在A中)插入B.

因此，如果A是由以下节点构建的：

Node(value : int, left : Option[Node], right : Option[Node])

value订购

然后B将由元节点构建，如：

MetaNode(value : Node, left : Option[MetaNode], right : Option[MetaNode])

value.value订购

用MetaNode(A.head)作为其唯一元素初始化B

然后重复执行：

for i in range 0..k-1:
current = B.pop.value
B.push (current.left) //might be None, should be coded so this is a no-op
B.push (current.right) //see above
results.add(current.value)

这不是我描述过的最简单的算法，所以如果有什么不清楚的地方，请问，我会尽量更清楚地描述它。：)

Answer 2

我不知道你为什么认为你需要二进制搜索。堆的意义在于不需要这样做。

请记住，堆中的关键操作如下：

1. Append-在末尾添加一个元素
2. CCD_ 13交换两个元素
3. CCD_ 14—取一个元素；跌倒"；到它的位置。也就是说，当它不是根并且比它的父对象大时，您Swap它和它的父节点并继续。(请注意，在指针版本中，您不是通过比较指针进行比较，而是通过比较指针所指向的值进行比较。原理是一样的，但您可能需要重写堆代码才能进行比较。)
4. HeapInsert-您先Append，然后SiftDown
5. SiftUp-与SiftDown相反。虽然元素有子元素，并且至少比一个子元素小，但可以将其与较大的子元素交换，然后继续
6. HeapPop-您Swap第一个和最后一个元素，将最后一个移除到临时变量中，SiftUp第一个元素，然后返回以前的第一个元素

通过这些操作，您的伪代码变为：

Print_k_largest(A[1,…,n],k):
If k>Heapsize(A):Error
i=1
HeapInsert[B,pointer to A[i]])
While k>0:
if 2*i< Heapsize(A):
HeapInsert(B,pointer to A[2*i])
HeapInsert(B,pointer to A[2*i+1])
elif 2*i= Heapsize(A):
HeapInsert(B,pointer to A[2*i])
PtrToElement = HeapPop(B)    
print(PtrToElement.value)      
k-=1

如果您在使用本机指针的语言(如C)中工作，则可以使用&(也称为"地址")和*(也称为所指向的对象)运算符非常容易地构造指针。如果使用没有指针的语言，则需要将索引存储到A中，如i和j，然后使用A[i]和A[j]获取值。这意味着CCD_；指针"；因为该语言不支持实际的指针。

无论哪种方式，你实际上都需要实施自己的"；指针堆"；。

在Python中我作弊。我将使用元组，而不是在堆中使用整数。所以我最终存储了(A[i], i)。因此，我将值和索引存储在一起，并首先按值进行比较。如果您的语言具有动态类型和元组，那么这可能比重写堆实现更方便。但我怀疑你使用的语言是否会支持这个技巧。

Answer 3

您必须创建一个临时的Max二进制堆，并删除节点(k-1)时间，每次删除时都在堆上执行下堆操作。之后，您可以简单地打印节点，它是堆中第K个最大的元素。时间复杂度-O(K*LogK)