Heap became unsorted while calling heappush

[PC-Killer]

Bug report

Bug description:

Read the code below:

import heapq


heap = []
heapq.heappush(heap, (2, 2))
heapq.heappush(heap, (1, 2))
heapq.heappush(heap, (1, -1))
print(heap)

It is very simple, and obviously, it should print "[(1, -1), (1, 2), (2, 2)]".
But here is what it prints:

PC-Killer@nixos ~> python --version ; cat -n ~/python_work/bugs/unordered_heap.py ; python ~/python_work/bugs/unordered_heap.py
Python 3.14.0a4
     1  import heapq
     2
     3
     4  heap = []
     5  heapq.heappush(heap, (2, 2))
     6  heapq.heappush(heap, (1, 2))
     7  heapq.heappush(heap, (1, -1))
     8  print(heap)
[(1, -1), (2, 2), (1, 2)]

The heap became unsorted.

CPython versions tested on:

3.14

Operating systems tested on:

Linux

[graingert]

heapq doesn't need to maintain a sorted list, it just needs to maintain a heap invariant such that heappop returns the smallest item.

import heapq

items = [(2, 2), (1, 2), (1, -1)]

heap = []
heapq.heappush(heap, items[0])
heapq.heappush(heap, items[1])
heapq.heappush(heap, items[2])

items2 = [
    heapq.heappop(heap),
    heapq.heappop(heap),
    heapq.heappop(heap),
]
assert items2 == sorted(items)
print(items2)

You could open a discussion in https://discuss.python.org/c/help/7