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

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

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

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

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