Учитывая список переходов, лучший способ создать двоичную Min/Max Heap?Построение Min/Max Binary Heap
Я пытаюсь ограничить с помощью следующих конструкций:
Нет массив, который будет использоваться в двоичной куче. Реализация основана на узлах. BinaryNode { value, parent, l_child, r_child }
Давайте просто придерживаться Max-Heap.
Вопрос: Можем ли мы сделать лучше, чем стандартные вставки, которая включает в себя BubbleDown.
Существует элегантный алгоритм линейного времени для построения макс-кучи из набора значений, который асимптотически быстрее, чем просто выполнение n шагов пузырька. Идея состоит в том, чтобы построить лес с меньшими макс-кучами, а затем последовательно объединить их вместе, пока все элементы не будут объединены в одну максимальную кучу. Используя точный анализ, можно показать, что этот алгоритм работает в O (n) времени с очень хорошим постоянным множителем. К ним относятся многие стандартные библиотеки; например, C++ имеет алгоритм std::make_heap.
Для получения более подробной информации об этом алгоритме, в том числе эскиза алгоритма, корректность доказательства, и анализа выполнения, проверить это ранее вопрос: https://stackoverflow.com/a/6300047/501557
Надеется, что это помогает!
Вы считаете, что куча представляет собой полное двоичное дерево? Или это любое дерево, которое подчиняется свойству кучи? – templatetypedef
«Полное двоичное дерево», а не любое дерево. –