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

本文介绍了最大堆中的第K个最大元素的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

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

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/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/ebooks/An%20Optimal%20Algorithm%20for%20Selection%20in%20a%20Min-Heap.pdf