Построение мин / макс двоичной кучи - PullRequest
Новая
       58

Построение мин / макс двоичной кучи

2 голосов
/ 26 декабря 2011

Учитывая список обхода по порядку, каков наилучший способ создания двоичной минимальной / максимальной кучи?

Я пытаюсь ограничиться следующими конструкциями:

  1. Нет массива для использования в двоичной кучи. Реализация основана на узлах. BinaryNode { value, parent, l_child, r_child }

  2. Давайте просто придерживаться Max-Heap.

Вопрос: Можем ли мы сделать лучше, чем стандартная вставка, которая включает BubbleDown.

1 Ответ

3 голосов
/ 26 декабря 2011

Существует элегантный алгоритм линейного времени для построения максимальной кучи из набора значений, который асимптотически быстрее, чем просто делает n пузырьковых шагов.Идея состоит в том, чтобы создать лес меньших максимальных куч, а затем непрерывно объединять их попарно, пока все элементы не будут объединены в одну максимальную кучу.Используя точный анализ, можно показать, что этот алгоритм выполняется за O (n) времени с очень хорошим постоянным коэффициентом.Многие стандартные библиотеки включают эту функцию;например, C ++ имеет алгоритм std::make_heap.

Для получения более подробной информации об этом алгоритме, включая эскиз алгоритма, доказательство корректности и анализ времени выполнения, проверьте этот предыдущий вопрос: https://stackoverflow.com/a/6300047/501557

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

...