Посты с тэгом куча


Решаем задачи без самобалансирующихся деревьев в Python

Многие задачи на алгоритмы требуют знания определённых структур данных. Стек, очередь, куча, динамический массив, двоичное дерево поиска — нечасто решение алгоритмической задачи обходится без использования чего-либо из них. Однако, качественная их реализация — нетривиальная задача, и при написании кода всегда хочется по максимуму обойтись использованием стандартной библиотеки языка.

Что касается Python, то в нём есть почти всё.

  • Динамический массив — встроенный тип list. Он же поддерживает и стековые операции: .append() и .pop().
  • Хэш-таблица — встроенные типы set и dict, а также неизменяемый брат сета frozenset.
  • Куча — list со специальными операциями вставки и удаления, реализованными в модуле heapq.
  • Двусторонняя очередь — это описанный в модуле collections тип deque.

Но вот само