Построение кучи сверху вниз при получении элемента по одному

поэтому я читал, что когда вы получаете элементы один за другим, вы должны использовать построение кучи снизу вверх, а не кучи сверху вниз, но что, если я использую алгоритм heapify каждый раз, когда добавляю новый элемент, в основном делая то же самое из n/ 2 к 1 heapify (i) каждый раз, когда я добавляю элемент в массив, каковы недостатки этого подхода в отношении использования построения кучи с разбивкой вверх и какова временная сложность


time-complexity heap topdown bottom-up heapsort
person Tarun Prakash Singh    schedule 31.03.2020    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Метод 'build-heap' (то, что вы называете построением сверху вниз) - это O (n). Таким образом, каждая вставка в кучу будет операцией O(n). Сравните это со вставкой снизу и просеиванием вверх, что в худшем случае составляет O(log n), но на практике ближе к O(1). См. Аргумент для O(1) средней сложности вставки кучи.

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

person Jim Mischel    schedule 01.04.2020