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