最大堆中的第K个最大元素

Question

我想提出一些方法来解决以下问题:

给定表示为数组的max-heap,返回第k个最大元素而不修改堆.我被要求在线性时间内完成,但被告知可以在日志时间内完成.

我想到了一个解决方案:

使用第二个最大堆并将其填入k或k + 1值(宽度优先遍历到原始值)然后弹出k个元素并获得所需的值.我想这应该是O(N + logN)= O(N)

是否有更好的解决方案,也许是在O(logN)时间？

Answer 1

max-heap可以有多种方式,更好的情况是完整的排序数组,而在其他极端情况下,堆可以具有完全不对称的结构.

这里可以看到:

在第一种情况下,第k个lagest元素位于第k个位置,您可以使用堆的数组表示在O(1)中进行计算.但是,通常,您需要检查(k,2k)元素,并对它们进行排序(或与另一个堆进行部分排序).据我所知,它是O(K·log(k))

而算法:

Input:
    Integer kth <- 8
    Heap heap <- {19,18,10,17,14,9,4,16,15,13,12}

BEGIN
    Heap positionHeap <- Heap with comparation: ((n0,n1)->compare(heap[n1], heap[n0]))

    Integer childPosition
    Integer candidatePosition <- 0
    Integer count <- 0
    positionHeap.push(candidate)
    WHILE (count < kth) DO
        candidatePosition <- positionHeap.pop();
        childPosition <- candidatePosition * 2 + 1
        IF (childPosition < size(heap)) THEN
            positionHeap.push(childPosition)
            childPosition <- childPosition + 1
            IF (childPosition < size(heap)) THEN
                positionHeap.push(childPosition)
            END-IF
        END-IF
        count <- count + 1
    END-WHILE
    print heap[candidate]
END-BEGIN

EDITED

我在这里找到了Frederickson的"最佳选择最佳算法":ftp: //paranoidbits.com/ebooks/An%20Optimal%20Algorithm%20for%20Selection%20in%20a%20Min-Heap.pdf

Answer 2

不，没有 O(log n) 时间算法，通过一个简单的单元探测下限。假设 k 是 2 的幂（不失一般性）并且堆看起来像（最小堆传入，因为它更容易标记，但没有真正的区别）

      1
   2     3
  4 5   6 7
.............
permutation of [k, 2k).

在最坏的情况下，我们必须读取整个排列，因为没有堆强加的顺序关系，只要没有找到 k，它就可以在任何尚未检查的位置。这需要时间 Omega(k)，匹配 templatetypedef 发布的（复杂！）算法。

Answer 3

据我所知，没有简单的算法可以解决这个问题。我所知道的最好的算法是 Frederickson 提出的，但这并不容易。您可以在此处查看该论文，但它可能位于付费专区后面。它的运行时间为 O(k)，这被认为是最好的时间，所以我怀疑不存在对数时间解决方案。

如果我找到比这更好的算法，我一定会让你知道。

希望这可以帮助！