Реализация макс-кучи в Python

Question

Реализация макс-кучи в Python

Рейтинг: 0Ответов: 1Опубликовано: 06.06.2023

В цикле обрабатывается команда из промта: если в команде нет 'insert' или 'pop' или 'end', то значит идёт ряд чисел в формате str. При этом условии я добавляю в кучу отрицательные значения из промта, чтобы реализовать макс-кучу.

from heapq import heappop, heappush, heapify

heap = []
heapify(heap)

while (promt:= input()) != 'end':
    if 'insert' or 'pop' not in promt:
        for p in promt.split():
            heappush(heap, -1 * int(p))
    elif 'insert' in promt:
        heappush(heap, -1 * int(promt.split()[1]))
    elif 'pop' in promt:
        print(-1 * (heappop(heap)))

при этом вылетает ошибка:

ValueError: invalid literal for int() with base 10: 'insert'

получается 'insert' игнорирует условие или как? Подскажите, где я мог допустить ошибку

На вход подаётся следующие значения:

1 5 2 6 3 7 4 8
insert 20
pop
insert 0
pop
insert 4
pop
end

python

Источник: Stack Overflow на русском

Answer 1

▲ 1Принят

_{Связанный вопрос: Неправильно работает сравнение переменной с несколькими значениями через or}

Условие if 'insert' or 'pop' not in promt: работает совсем не так, как вы думаете:

or не перечисляет значения справа и слева от него, а является логической операцией (логическое "ИЛИ", оно же дизъюнкция). В Python он имеет имеет дополнительные особенности: он возвращает первое не ложное значение среди его операндов.

'insert' or 'pop' not in promt на самом деле вычисляется как 'insert' or ('pop' not in promt), и результатом or будет первое не ложное значение среди его операндов, в данном случае - 'insert' (т.к. любая не пустая строка считается истинным значением), до вычисления ('pop' not in promt) дело вообще не дойдет. В итоге ваш if превратится в if 'insert':, "условие" у него всегда истинно, поэтому всегда выполняется первая ветка if.

Даже если обернуть в скобки ('insert' or 'pop') not in promt - выражение в скобках превратится просто в 'insert', все выражение превратится в 'insert' not in promt.

Правильно ваше условие должно выглядеть так:

if 'insert' not in promt and 'pop' not in promt:

Между частями именно and, потому что для первой ветки нужно чтобы обе стороны не были истинными одновременно.

Тут полезно знать законы де Моргана (при внесении отрицания в скобки отрицание применяется к операндам, и при этом or меняется на and и наоборот). Если вынести отрицание за скобки, получится такое условие:

if not ('insert' in promt or 'pop' in promt):

Но вообще проще всего исправить, перенеся первую ветку if в else

if 'insert' in promt:
    heappush(heap, -1 * int(promt.split()[1]))
elif 'pop' in promt:
    print(-1 * (heappop(heap)))
else:
    for p in promt.split():
        heappush(heap, -1 * int(p))

Реализация макс-кучи в Python

Ответы