Как построение кучи может быть O (n) сложностью по времени?

Question

Может кто-нибудь помочь объяснить, как сборка кучи может быть O (n) сложностью?

Вставка элемента в кучу - O(log n), и вставка повторяется n / 2 раза (остальные - листья, и они не могут нарушать свойство кучи).Таким образом, это означает, что сложность должна составлять O(n log n), я бы подумал.

Другими словами, для каждого элемента, который мы «heapify», он может быть отфильтрован один раз для каждого уровня кучи.до сих пор (то есть log n уровней).

Чего мне не хватает?

Answer 1

Я думаю, что в этой теме похоронено несколько вопросов:

• Как реализовать buildHeap, чтобы он работал за O (n) время?
• Как вы показываете, что buildHeap работает правильно O (n) , когда реализовано правильно?
• Почему эта же логика не работает для выполнения сортировки кучи в O (n) время вместо O (n log n) ?

Как реализовать buildHeap, чтобы он работал в O (n) время?

Часто ответы на эти вопросы сосредоточены на разнице между siftUp и siftDown.Правильный выбор между siftUp и siftDown крайне важен для получения производительности O (n) для buildHeap, но не помогает понять разницу между buildHeap и heapSort вгенеральный.Действительно, правильные реализации как buildHeap, так и heapSort будут только использовать siftDown.Операция siftUp необходима только для вставки в существующую кучу, поэтому она будет использоваться для реализации очереди приоритетов, например, с использованием двоичной кучи.

Я написал это, чтобы описать, как макс.куча работает.Этот тип кучи обычно используется для сортировки кучи или для очереди с приоритетами, где более высокие значения указывают на более высокий приоритет.Мин куча также полезна;например, при извлечении элементов с целочисленными ключами в порядке возрастания или строк в алфавитном порядке.Принципы точно такие же;просто измените порядок сортировки.

Свойство heap указывает, что каждый узел в двоичной куче должен быть по крайней мере таким же большим, как оба его потомка.В частности, это означает, что самый большой элемент в куче находится в корне.Отбор и отбор - это, по сути, одна и та же операция в противоположных направлениях: перемещайте вызывающий беспокойство узел, пока он не удовлетворяет свойству кучи:

• siftDown меняет узел, который слишком мал, с его самым большим потомком (таким образом,перемещая его вниз), пока он не станет по крайней мере таким же большим, как оба узла под ним.
• siftUp меняет узел, который слишком велик, с его родителем (тем самым перемещая его вверх), пока он не станет больше, чем узел над ним.

Количество операций, необходимых для siftDown и siftUp, пропорционально расстоянию, которое может пройти узел.Для siftDown это расстояние до нижней части дерева, поэтому siftDown стоит дорого для узлов в верхней части дерева.При siftUp работа пропорциональна расстоянию до вершины дерева, поэтому siftUp стоит дорого для узлов в нижней части дерева.Хотя в худшем случае обе операции равны O (log n) , в куче только один узел находится сверху, тогда как половина узлов лежит на нижнем уровне.Так что не должно быть слишком удивительно, что если нам нужно применить операцию к каждому узлу, мы бы предпочли siftDown над siftUp.

Функция buildHeap принимаетмассив несортированных элементов и перемещает их, пока все они не удовлетворяют свойству кучи, тем самым создавая допустимую кучу.Существует два подхода, которые можно использовать для buildHeap, используя операции siftUp и siftDown, которые мы описали.

1. Начать с верхней части кучи (начало массива) и вызвать siftUp для каждого элемента.На каждом шаге ранее просеянные элементы (элементы перед текущим элементом в массиве) образуют правильную кучу, а отсеивание следующего элемента помещает его в допустимую позицию в куче.После просеивания каждого узла все элементы удовлетворяют свойству кучи.

2. Или идите в противоположном направлении: начните с конца массива и двигайтесь назад вперед.На каждой итерации вы просеиваете элемент до тех пор, пока он не окажется в правильном месте.

Какая реализация для buildHeap более эффективна?

Оба эти решения будутсоздать правильную кучу.Неудивительно, что наиболее эффективной является вторая операция, в которой используется siftDown.

Пусть h = log n представляет высоту кучи.Работа, требуемая для подхода siftDown, дается суммой

(0 * n/2) + (1 * n/4) + (2 * n/8) + ... + (h * 1).

Каждый член в сумме имеет максимальное расстояние, которое должен будет пройти узел на данной высоте (ноль для нижнего слоя, h для корня), умноженный на количество узлов на этой высоте.Напротив, сумма для вызова siftUp на каждом узле равна

(h * n/2) + ((h-1) * n/4) + ((h-2)*n/8) + ... + (0 * 1).

. Должно быть ясно, что вторая сумма больше.Один первый член равен hn / 2 = 1/2 n log n , поэтому этот подход в лучшем случае имеет сложность O (n log n) .

Как мы можем доказать, что сумма для подхода siftDown действительно O (n) ?

Один метод (есть и другие анализы, которые также работают) - этопревратить конечную сумму в бесконечный ряд, а затем использовать ряды Тейлора.Мы можем игнорировать первый член, который равен нулю:

Если вы не уверены, почему каждый из этих шагов работает, вот оправдание дляпроцесс в словах:

• Все члены положительны, поэтому конечная сумма должна быть меньше бесконечной суммы.
• Ряд равен степенному ряду, оцененному в x = 1/2 .
• Этот степенной ряд равен (постоянному времени) производной ряда Тейлора для f (x) = 1 / (1-x) .
• x = 1/2 находится в интервале сходимости этого ряда Тейлора.
• Следовательно, мы можем заменить ряд Тейлора на 1/ (1-x) , дифференцируем и оцениваем, чтобы найти значение бесконечного ряда.

Поскольку бесконечная сумма в точности равна n , мы заключаем, чтоконечная сумма не больше и поэтому составляет O (n) .

Почему для сортировки кучи требуется O (n log n) время?

Если возможно запустить buildHeap в линейном времени, почему сортировка кучи требует O (n log n) времени?Ну, куча сортировки состоит из двух этапов.Сначала мы вызываем buildHeap для массива, который требует O (n) времени, если реализовано оптимально.Следующим этапом является повторное удаление самого большого элемента в куче и помещение его в конец массива.Поскольку мы удаляем элемент из кучи, сразу после окончания кучи всегда есть открытое место, где мы можем сохранить элемент.Таким образом, сортировка кучи достигает отсортированного порядка, последовательно удаляя следующий по величине элемент и помещая его в массив, начиная с последней позиции и двигаясь вперед.Это сложность этой последней части, которая доминирует в куче.Цикл выглядит следующим образом:

for (i = n - 1; i > 0; i--) {
    arr[i] = deleteMax();
}

Ясно, что цикл выполняется O (n) раз (если быть точным, n - 1 , последний элемент уже на месте).Сложность deleteMax для кучи составляет O (log n) .Обычно это выполняется путем удаления корня (самый большой элемент, оставшийся в куче) и замены его последним элементом в куче, который является листом и, следовательно, одним из самых маленьких элементов.Этот новый корень почти наверняка нарушит свойство кучи, поэтому вы должны вызывать siftDown, пока не вернете его обратно в приемлемое положение.Это также приводит к перемещению следующего по величине элемента до корня.Обратите внимание, что в отличие от buildHeap, где для большинства узлов мы вызываем siftDown из нижней части дерева, теперь мы вызываем siftDown из верхней части дерева на каждой итерации! Хотя дерево сжимается, оно не сжимается достаточно быстро : Высота дерева остается постоянной, пока вы не удалите первую половину узлов (когда полностью очистите нижний слой).Затем для следующей четверти высота составляет ч - 1 .Таким образом, общая работа для этого второго этапа составляет

h*n/2 + (h-1)*n/4 + ... + 0 * 1.

Обратите внимание на переключатель: теперь нулевой рабочий случай соответствует одному узлу, а рабочий h соответствует половине узлов.Эта сумма равна O (n log n) , как и неэффективная версия buildHeap, реализованная с использованием siftUp.Но в этом случае у нас нет выбора, так как мы пытаемся отсортировать, и мы требуем, чтобы следующий самый большой элемент был удален следующим.

Таким образом, работа по сортировке кучи является суммой двух этапов: O (n) время для buildHeap и O (n log n) для удаления каждого узла в порядке , поэтому сложность O (n log n) . Вы можете доказать (используя некоторые идеи из теории информации), что для сортировки, основанной на сравнении, O (n log n) - это лучшее, на что вы могли бы надеяться в любом случае, так что нет причин разочаровываться этим или ожидайте, что сортировка кучи достигнет времени O (n), которое buildHeap делает.

Answer 2

Ваш анализ верен.Тем не менее, это не тесно.

Нелегко объяснить, почему построение кучи является линейной операцией, вам лучше ее прочитать.

A отличный анализ алгоритма можно увидеть здесь .

---

Основная идея заключается в том, что в алгоритме build_heap фактическая стоимость heapify не равна O(log n) для всех элементов.

Когда *Вызывается 1017 *, время выполнения зависит от того, насколько далеко элемент может переместиться вниз по дереву до завершения процесса.Другими словами, это зависит от высоты элемента в куче.В худшем случае элемент может опуститься до уровня листа.

Давайте посчитаем выполненную работу уровень за уровнем.

На самом нижнем уровне есть 2^(h) узлы, но мы не вызываем heapify ни на одном из них, поэтому работаравно 0. На следующем уровне есть 2^(h − 1) узлов, и каждый может сдвинуться вниз на 1 уровень.На 3-м уровне снизу есть 2^(h − 2) узлов, и каждый может сдвинуться вниз на 2 уровня.

Как видите, не все операции heapify O(log n), поэтому вы получаете O(n).

Answer 3

Наглядно:

"Сложность должна быть O (nLog n) ... для каждого элемента, который мы" heapify ", у него есть потенциальная необходимость фильтровать один раз для каждого уровня кучи до сих пор (то есть log n уровней). «

Не совсем. Ваша логика не дает жесткой границы - она ​​переоценивает сложность каждой кучи. Если построено снизу вверх, вставка (heapify) может быть намного меньше чем O(log(n)). Процесс выглядит следующим образом:

(Шаг 1) Первые n/2 элементы идут в нижний ряд кучи. h=0, поэтому heapify не требуется.

(Шаг 2) Следующие n/2<sup>2</sup> элементы идут в строке 1 снизу вверх. h=1, фильтры heapify на 1 уровень ниже.

(Шаг i ) Следующие элементы n/2<sup>i</sup> идут в строку i снизу вверх. h=i, фильтры heapify i уровни понижены.

(Шаг log (n) ) Последний элемент n/2<sup>log<sub>2</sub>(n)</sup> = 1 идет в строку log(n) снизу вверх. h=log(n), фильтры heapify log(n) уровни понижены.

ВНИМАНИЕ: что после первого шага 1/2 элементов (n/2) уже находятся в куче, и нам даже не нужно было вызывать heapify один раз. Кроме того, обратите внимание, что только один элемент, корень, на самом деле несет полную log(n) сложность.

---

Теоретически:

Всего шагов N для построения кучи размером n можно записать математически.

На высоте i мы показали (выше), что будет n/2<sup>i+1</sup> элементов, которые должны вызывать heapify, и мы знаем, что heapify на высоте i равна O(i). Это дает:

Решение последнего суммирования можно найти, взяв производную обеих сторон хорошо известного уравнения геометрической серии:

Наконец, добавив x = 1/2 в вышеприведенное уравнение, вы получите 2. Включение этого в первое уравнение дает:

Таким образом, общее количество шагов имеет размер O(n)

Answer 4

Было бы O (n log n), если бы вы строили кучу, многократно вставляя элементы.Однако вы можете создать новую кучу более эффективно, вставляя элементы в произвольном порядке, а затем применяя алгоритм для «кучи» их в правильном порядке (конечно, в зависимости от типа кучи).1003 *http://en.wikipedia.org/wiki/Binary_heap, "Создание кучи" для примера.В этом случае вы, по сути, работаете с нижнего уровня дерева, меняя местами родительский и дочерний узлы, пока не будут выполнены условия кучи.

Answer 5

Как мы знаем, высота кучи равна log (n) , где n - общее количество элементов. Позволяет представить его как h
Когда мы выполняем heapifyоперации, то элементы на последнем уровне ( h ) не будут перемещаться даже на один шаг.
Количество элементов на втором последнем уровне ( h-1 ) равно 2 ^ч-1 и они могут двигаться на максимальном уровне 1 (во время heapify).
Аналогично, для уровня i ^{th ,} мы имеем 2 ⁱ элементы, которые могут перемещаться привет позиции.

Поэтому общее количество ходов = S = 2 ^{ч * +1043 ** 0 + 2 * ** 1047 тысячу сорок-шесть * ч-1 * 1 048 *}* 1 + 2 * +1052 ** * ч тысяча пятьдесят три-2 * 2 + ... 2 ⁰ * ч

S = 2 ^ч {1/2 + 2/2 ² +3/2 ³ + ... ч / 2 ^ч } ------------------------------------------------- 1
этосоставляет AGP серии, чтобы решить это деление обеих сторон на 2
S / 2 = 2 ^ч {1/2 ² + 2/2 ³ + ... ч / 2 ^{ч + 1} } ​​ ------------------------------------------------- 2
вычитая уравнение 2 из 1 дает
S / 2 = 2 ^ч {1/ 2 + 1/2 ² + 1/2 ³ +... + 1/2 ^ч + ч / 2 ^{ч + 1} }
S = 2 ^{ч + 1} {1/2 + 1/2 ² + 1/2 ³ + ... + 1/2 ^ч + ч / 2 ^{ч + 1} }
сейчас 1/2+ 1/2 ² + 1/2 ³ + ...+ 1/2 ^ч уменьшается ГП , чья сумма меньше 1 (когда h стремится к бесконечности, суммастремится к 1).В дальнейшем анализе, давайте возьмем верхнюю границу суммы, которая равна 1.
Это дает S = 2 ^{h + 1} {1+ ч / 2 ^{ч + 1} }
= 2 ^{ч + 1} + ч
~ 2 ^ч + ч
as h = log (n) , 2 ^h = n

Следовательно S = n + log (n)
T (C) = O (n)

Answer 6

Уже есть несколько отличных ответов, но я хотел бы добавить небольшое визуальное объяснение

Теперь взгляните на изображение:
n/2^1 зеленые узлы с высота 0 (здесь 23/2 = 12)
n/2^2 красные узлы с высота 1 (здесь 23/4 = 6)
n/2^3 синий узел с высота 2 (здесь 23/8 = 3)
n/2^4 фиолетовые узлы с высотой 3 (здесь 23/16 = 2)
, поэтому есть n/2^(h+1) узлов для высоты ч
Чтобы найтивременная сложность позволяет подсчитать объем выполненной работы или макс. число итераций, выполненных каждым узлом
, теперь можно заметить, что каждый узел может выполнять (максимум) итераций== высота узла

Green = n/2^1 * 0 (no iterations since no children)  
red   = n/2^2 * 1 (*heapify* will perform atmost one swap for each red node)  
blue  = n/2^3 * 2 (*heapify* will perform atmost two swaps for each blue node)  
purple = n/4^3 * 3  

, поэтому для любых узлов с высотой h максимальное количество выполненных работ составляет n / 2 ^ (ч+1) * h

Теперь общая выполненная работа составляет

->(n/2^1 * 0) + (n/2^2 * 1)+ (n/2^3 * 2) + (n/2^4 * 3) +...+ (n/2^(h+1) * h)  
-> n * ( 0 + 1/4 + 2/8 + 3/16 +...+ h/2^(h+1) ) 

для любого значения ч , последовательность

-> ( 0 + 1/4 + 2/8 + 3/16 +...+ h/2^(h+1) ) 

никогда не будет превышать 1
Таким образом, сложность времени никогда не будет превышать O (n) для кучи здания

Answer 7

При построении кучи предположим, что вы подходите снизу вверх.

1. Вы берете каждый элемент и сравниваете его с дочерними элементами, чтобы проверить, соответствует ли пара правилам кучи.Таким образом, листья включаются в кучу бесплатно.Это потому что у них нет детей.
2. При движении вверх наихудшим сценарием для узла прямо над листьями будет 1 сравнение (при максимуме их можно сравнить с одним поколением детей)родителей можно максимально сравнить с двумя поколениями детей.
3. Продолжая в том же направлении, вы получите сравнение журнала (n) для корня в худшем случае.и log (n) -1 для его непосредственных потомков, log (n) -2 для их непосредственных потомков и т. д.
4. Итак, подведя итог, вы получите что-то вроде log (n) + {log(n) -1} * 2 + {log (n) -2} * 4 + ..... + 1 * 2 ^ {(logn) -1}, что является ничем иным, как O (n).

Answer 8

В случае построения кучи, мы начинаем с высоты, logn -1 (где logn - высота дерева из n элементов). Для каждого элемента, находящегося на высоте 'h', мы идем на максимум вверх (logn -h) вниз.

    So total number of traversal would be:-
    T(n) = sigma((2^(logn-h))*h) where h varies from 1 to logn
    T(n) = n((1/2)+(2/4)+(3/8)+.....+(logn/(2^logn)))
    T(n) = n*(sigma(x/(2^x))) where x varies from 1 to logn
     and according to the [sources][1]
    function in the bracket approaches to 2 at infinity.
    Hence T(n) ~ O(n)

Answer 9

Доказательство O (n)

Доказательство не является причудливым и довольно простым, я только доказал случай для полного двоичного дерева, результат можно обобщить для полного двоичного дерева.

Answer 10

@ bcorso уже продемонстрировал доказательство сложности анализа.Но ради тех, кто все еще изучает анализ сложности, я должен добавить следующее:

В основе вашей первоначальной ошибки лежит неверное истолкование значения утверждения: «вставка в кучу требует O (logо) время ".Вставка в кучу - это действительно O (log n), но вы должны признать, что n - это размер кучи во время вставки .

В контексте вставки n объектов вкуча, сложность i-й вставки составляет O (log n_i), где n_i - размер кучи, как при вставке i.Только последняя вставка имеет сложность O (log n).