Построить Min-Max Heap за O(n) сложность по времени

Question

Согласно википедии, это минимальная куча: https://en.wikipedia.org/wiki/Min-max_heap. Мне было интересно, есть ли способ построить эту кучу min-max в O(n). Я знаю, что вы можете сделать это как с минимальной кучей, так и с максимальной кучей, но я не уверен, каков будет подход к этому. Вставка элемента требует O(log n) временной сложности, и я чувствую, что такое дерево не может быть построено более эффективно, чем O(n log n), но я надеюсь, что у кого-то есть ответ. Благодарю.

Answer 1

Да, оно может. В вашем цикле сборки-кучи вы просто вызываете TrickleDownтак же, как вы бы с минимальной кучей или максимальной кучей. Эта функция будет перемещать элемент соответственно, в зависимости от того, находится ли он на минимальном или максимальном уровне.

См. Оригинальную статью Min-Max Heaps и Generalized Priority Queues для общей информации. В статье не реализована сборка кучи, но если вы напишите свой собственный, то вызовы TrickleDownработает как положено. То есть:

for i = A.length/2 downto 0
    TrickleDown(i)

TrickleDown определяет, если i находится на минимальном уровне или максимальном уровне, и вызывает соответствующий метод, TrickleDownMin или же TrickleDownMax,