Python: Почему куча дает неправильный первый поп?

Question

Я пытаюсь создать максимальную кучу, отрицая все значения списка, но, похоже, это не работает:

import heapq
x = range(1,10)
neg = [-n for n in x]
heapq.heappop(neg) # -1
heapq.heappop(neg) # -9
heapq.heappop(neg) # -8

И все же, если я сделаю

heapq.heappop(x) # 1
heapq.heappop(x) # 2
heapq.heappop(x) # 3

Кажется, работает правильно.Есть идеи, почему возвращается -1?

Answer 1

heapq.heappop - это только для minheaps;вы не можете просто создать maxheap и ожидать, что функции на основе minheap будут работать над ним, потому что он не соблюдает инвариант minheap.

Если цель состоит в том, чтобы сначала получить -9, вам нужнокуча поддерживает правильные инварианты, сначала (по сути, O(n)), хапифицируя его:

heapq.heapify(neg)

, после чего ваш код выскочит с -9 до -1.

Если вы 'пытаясь получить максимальную выгоду, это не поддерживается Все официально задокументированные функции heapq работают с minheaps (выделение добавлено):

Приведенный ниже API отличается от алгоритмов кучи учебников в двух аспектах: (a) Мы используем ноль-на основе индексации.Это делает связь между индексом для узла и индексами для его дочерних элементов несколько менее очевидной, но является более подходящей, поскольку Python использует индексацию с нуля.(b) Наш метод pop возвращает наименьший элемент, а не наибольший (в учебниках он называется «min heap»; «max heap» чаще встречается в текстах из-за его пригодности для сортировки на месте).

В модуле есть несколько выбранных (и недокументированных) функций на основе maxheap, которые будут работать, например, heapq._heappop_max, но они не являются документированной частью API и могут измениться илиисчезнуть в любое время.

Answer 2

Вы не должны использовать heappush/heappop, если у вас не поддерживается инвариант кучи.

Чтобы создать кучу из существующего списка, используйте heapq.heapify(mylist).

>>> neg = [-n for n in range(1,10)]
>>> neg[0]  # peek
-1
>>> heapq.heapify(neg)
>>> neg[0]  # peek
-9
>>> -heapq.heappop(neg)  # largest element
9