Kth largest element in a max-heap

Question

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

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:

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)

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

Answer 1

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:

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))

And the algorithm:

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

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

Answer 2

No, there's no O(log n)-time algorithm, by a simple cell probe lower bound. Suppose that k is a power of two (without loss of generality) and that the heap looks like (min-heap incoming because it's easier to label, but there's no real difference)

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

In the worst case, we have to read the entire permutation, because there are no order relations imposed by the heap, and as long as k is not found, it could be in any location not yet examined. This takes time Omega(k), matching the (complicated!) algorithm posted by templatetypedef.