最大堆中第K大的元素

Question

最大堆中第K大的元素

algorithmdata-structuresheappseudocode

16

我正在努力想出解决以下问题的方法：

给定一个用数组表示的最大堆，返回第k大的元素而不修改堆。我被要求在线性时间内完成，但被告知可以在对数时间内完成。

我想到了一种解决方案：

使用第二个最大堆并将k或k+1个值填充进去（广度优先遍历原始堆），然后弹出k个元素并获取所需元素。我认为这应该是O(N+logN)=O(N)。

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

- Alstor

明白了，谢谢。但在这种情况下，我仍然认为你的算法不正确，因为树的广度优先搜索行不通，对吧？ - sunny

我想它应该可以工作。我错误地使用了“搜索”这个术语，基本上我只是在寻找一种遍历方式，可以存储一个层级的节点，然后继续下一层。我将编辑术语以消除任何潜在的歧义。 - Alstor

1

我认为斐波那契堆是实现摊销O(log n)解决方案的途径，但我喜欢这个问题。我会好好思考一下... - erip

1

@Alstor，我认为你的解决方案不正确，因为第k大的元素不一定在树的第k层。 - Sumeet

提示：您必须使用堆操作。对于堆而言，“广度优先遍历”没有意义。 - Colonel Panic

显示剩余2条评论

4个回答

5

没有O(log n)时间复杂度的算法，这是因为基于简单的细胞探针下界。假设k是2的幂次方（不失一般性），堆看起来像（最小堆入队，因为容易标记，但实际上没有实质区别）。

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

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

- David Eisenstat

标题说的是最大堆中的第K大元素（不是任意数组）。因此不存在最小堆的问题。您所概述的最坏情况并不适用，因为它是最大堆，所以父节点始终比其子节点高。 - Kishore

1

@Kishore 我回答的重点是堆结构在最坏情况下并不会施加太多的限制。 - David Eisenstat

2

据我所知，目前没有解决这个问题的简单算法。我所知道的最好的算法是由Frederickson提出的，但它并不容易。你可以在这里查看论文（可能需要付费）。该算法的运行时间为O(k)，据称这是最佳时间，因此我怀疑不存在对数时间的解决方案。

如果我找到比这更好的算法，我一定会告诉你。

希望这有所帮助！

- templatetypedef

2

数组中的最大堆：i为基于0的索引，i处的元素大于2*i+1和2*i+2处的元素。

您需要另一个最大堆（insert、pop、empty），其中包含按value排序的元素对(value, index)。伪代码（不包括边界检查）：

input: k
1. insert (at(0), 0)
2. (v, i) <- pop and k <- k - 1
3. if k == 0 return v
4. insert (at(2*i+1), 2*i+1) and insert (at(2*+2), 2*+2)
5. goto 2

运行时评估

数组访问 at(i): O(1)
插入到堆中: O(log n)
在第4个位置插入，最多需要 log(k) 的时间，因为成对堆的大小最多为 k + 1
语句3最多执行 k 次
总运行时间：O(k log k)

- BeyelerStudios

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- David Pérez Cabrera · Accepted Answer

最大堆可以有很多种形式，更好的情况是完全排序的数组，而在其他极端情况下，堆可能具有完全不对称的结构。

如图所示：

在第一种情况下，第k大的元素位于第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

我在这里找到了弗雷德里克森（Frederickson）撰写的“最小堆中选择的最优算法”： ftp://paranoidbits.com/ebooks/An%20Optimal%20Algorithm%20for%20Selection%20in%20a%20Min-Heap.pdf

EDITED