Кучи и деревья бинарного поиска

Question

1. Какое время выполнения связано с (Max-heapify), который реализован с использованием k-ary heap.
2. Является ли k-арная куча более эффективной, чем асимптотически говоря, двоичная куча?
3. Является ли k-ary куча более эффективной, чем двоичная куча на практике?
4. дерево поиска может быть реализовано как k-arry?

Answer 1

Вы задали много вопросов, поэтому я постараюсь ответить на все из них по очереди.

1. Время выполнения операции heapify для k-арной кучи равно O(n), которое не зависит от k. Это не сразу очевидно, но большинство учебников по вводным алгоритмам имеют доказательство этого результата для случая, когда k = 2.

2. Давайте сделаем анализ для k-арной кучи в целом, который мы затем можем сравнить с двоичной кучей, просто установив k = 2. В k-арной куче стоимость операции find-min составляет O(1) (просто посмотрите на верхнюю часть кучи), и стоимость операции кучи составляет O(n), как упоминалось выше. При добавлении нового элемента в k-арную кучу время выполнения пропорционально высоте кучи, которая равна O (log_k n) = O(log n / log k) (что следует из использования изменения базовая формула для логарифмов). Не принято включать основание логарифма в нотацию big-O, но в этом случае, поскольку k является параметром, мы не можем игнорировать его вклад. В операции извлечения мин нам нужно работать сверху вниз по дереву. На каждом уровне мы просматриваем до k дочерних элементов текущего узла, чтобы найти наибольшее, а затем потенциально выполняем обмен вниз. Это означает, что существует O(k) работа для каждого слоя, и есть O(log n / log k) слоев, поэтому работа сделана за O(k log n / log k). Асимптотически для любого фиксированного k время выполнения этих операций составляет O(1), O(n), O(log n) и O(log n), соответственно, поэтому нет асимптотической разницы между k-арной кучей и двоичная куча.

3. На практике, однако, есть различия. Один хороший способ увидеть это - сделать k действительно очень большим (скажем, 10¹⁰⁰). В этом случае стоимость удаления будет довольно большой, поскольку на узел будет приходиться до 10¹⁰⁰ дочерних элементов, что приведет к уменьшению высоты соответствующего двоичного дерева. Для средних значений k (k = 3 или 4) есть вероятность, что на самом деле может быть быстрее использовать 3-рядное или 4-разрядное дерево над двоичным деревом, но на самом деле лучший способ выяснить это - профилировать это и посмотрим, что получится. Взаимодействия таких факторов, как локальность ссылок, кэширование и скорость деления, будут конкурировать друг с другом, чтобы повлиять на время выполнения.

4. Да! Существуют такие вещи, как многоходовые поисковые деревья. Одним из наиболее известных из них является B-дерево, которое на самом деле представляет собой довольно забавную структуру данных для чтения.

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