Всем привет.

Подскажите, пожалуйста, как можно организовать работу с кучей
Добавление элемента (O(log n))\ извлечение max элемента (верхушки кучи) (O(n)) ?

В результате добавления происходит автобалансировка кучи ?

Заранее спасибо

FishHookСтанислав Клевцов,

чем не нравится встроенный тип dict?

океу.
За сколько O-большое можно добавить новый элемент в нужное место в dict ? (Думаю это O(n) 1 проход по всему dict + операция вставки О(1) или я не прав ?

FishHookСтанислав Клевцов,

чем не нравится встроенный тип dict?

Вот еще немного теории

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

Если же хранить элементы в списке упорядочив их по неубыванию, то извлечение наибольшего будет занимать O(1), но добавление элемента в список - O(n), так как придется сдвигать элементы, уже находящиеся в списке.

Специальная структура данных «Куча» (англ. heap) позволяет эти операции выполнять за O(log n)."

FishHookСтанислав Клевцовможно добавить новый элемент в нужное место в dict ?
dict - это хэш таблица, у неё нет позиции элемента.

Сорри, тогда как искать максимальный элемент в "словаре"?

FishHookСтанислав Клевцовможно добавить новый элемент в нужное место в dict ?
dict - это хэш таблица, у неё нет позиции элемента.

"Меньше вопросов, больше дела" Сам разобрался с задачей и решил её с помощью кучи
(где поиск макс\мин элемента за O(1),а также его удаление за O(1). Добавление новых элементов за O(log n)

А что касается dict, то поиск за O(1), но тупняки на добавлении и удалении элемента O(n).

Можно подвести итог. Для решения моей задчи dict не подходит, т.к. кушает много памяти на n-> 10^6 и не проходит по тестам системы.

Всем спасибо. Тема закрыта !

FishHook, библиотека "heapq"

Хеш-таблица требует предварительной инициализации ячеек значениями NULL
- трудоемкость O(h)




Пример :