Конструкция кучи сверху вниз при получении элемента один за другим

Question

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

Answer 1

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

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