Наибольший элемент Kth в макс-куче

Я пытаюсь придумать что-то, чтобы решить следующее:

Учитывая максимальную кучу, представленную как массив, верните k-й наибольший элемент без изменения кучи. Меня попросили сделать это в линейном времени, но мне сказали, что это можно сделать в режиме журнала.

Я думал о решении:

Используйте вторую максимальную кучу и заполните ее с помощью k или k + 1 значений в ней (ширина первого обхода в исходную), затем введите k элементов и получите желаемый. Я полагаю, что это должно быть O (N + logN) = O (N)

Есть ли лучшее решение, возможно, в O (logN)?

Ответ 1

Макс-куча может иметь много способов, лучший случай - это полный отсортированный массив, а в другом случае - куча может иметь общую асимметричную структуру.

Здесь можно увидеть следующее:

В первом случае 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

отредактированы

Я нашел "Оптимальный алгоритм отбора в мини-куче" Фредериксона здесь: ftp://paranoidbits.com/ebooks/An%20Optimal%20Algorithm%20for%20Selection%20in%20a%20Min-Heap.pdf

Ответ 2

Нет, нет алгоритма O (log n) -time, с помощью простой нижней оценки зонда ячейки. Предположим, что k является степенью двух (без потери общности) и что куча выглядит как (дерьмо, min-heap входящий, но это не имеет значения)

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

В худшем случае мы должны прочитать всю перестановку, потому что не существует никаких отношений порядка, наложенных кучей, и пока k не будет найдено, оно может быть в любом месте, которое еще не было проверено. Это требует времени Omega (k), соответствующего алгоритму (сложному!), Отправленному templatetypedef.

Ответ 3

Насколько я знаю, нет простого алгоритма для решения этой проблемы. Лучший алгоритм, который я знаю, принадлежит Фредериксону, и это непросто. Здесь вы можете проверить бумагу но это может быть за платной линией. Оно работает во времени O (k), и это, как утверждается, является наилучшее возможное время, поэтому я подозреваю, что решение для журнала не существует.

Если я нахожу лучший алгоритм, чем этот, я обязательно сообщу вам.

Надеюсь, это поможет!

Ответ 4

Макс. куча в массиве: element at i is larger than elements at 2*i+1 and 2*i+2 (i - 0)

Вам понадобится другая максимальная куча (insert, pop, empty) с парами элементов (value, index), отсортированными по value. Псевдокод (без пограничных проверок):

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

Оценка времени выполнения

доступ к массиву в (i): O (1)
Вставка в кучу: O (log n)
вставка 4. занимает не более log (k), так как размер кучи пар не более k + 1
утверждение достигается не более чем в k раз
общая продолжительность выполнения: O (k log k)