最大堆中的第K个最大元素 [英] Kth largest element in a max-heap

问题描述

我正在尝试解决以下问题：

I'm trying to come up with something to solve the following:

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

Given a max-heap represented as an array, return the kth largest element without modifying the heap. I was asked to do it in linear time, but was told it can be done in log time.

我想到了一个解决方案：

I thought of a solution:

使用第二个max-heap并在其中填充k或k + 1个值（首先遍历原始值），然后弹出k个元素并获得所需的一。我想这应该是O（N + logN）= O（N）

Use a second max-heap and fill it with k or k+1 values into it (breadth first traversal into the original one) then pop k elements and get the desired one. I suppose this should be O(N+logN) = O(N)

有没有更好的解决方案，也许是在O（logN）时间内？

Is there a better solution, perhaps in O(logN) time?

推荐答案

max-heap可以有多种方式，更好的情况是完整的排序数组，在​​其他极端情况下，堆可以具有总计不对称结构。

The max-heap can have many ways, a better case is a complete sorted array, and in other extremely case, the heap can have a total asymmetric structure.

在这里可以看到：

Here can see this:

在第一种情况下，第k个最大元素位于第k个位置，您可以在O（1）中使用数组表示形式进行计算堆。
但是，通常，您需要在（k，2k）个元素之间进行检查，并对它们进行排序（或对另一个堆进行部分排序）。据我所知，它是O（K·log（k））

In the first case, the kth lagest element is in the kth position, you can compute in O(1) with a array representation of heap. But, in generally, you'll need to check between (k, 2k) elements, and sort them (or partial sort with another heap). As far as I know, it's 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

I found "Optimal Algorithm of Selection in a min-heap" by Frederickson here: ftp://paranoidbits.com/ebooks/An%20Optimal%20Algorithm%20for%20Selection%20in%20a%20Min-Heap.pdf

这篇关于最大堆中的第K个最大元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！