A heap is not a sorted list: priority queue order and the 0-based index formulas
Why doesn't a printed heapq list or PriorityQueue look sorted? The heap invariant, 0-based parent/child formulas, costs versus a sorted list, and equal priorities.
Print a list after heapq.heapify and you might expect the values to appear smallest first. They don’t.
import heapq
h = [5, 3, 8, 1, 9, 2]
heapq.heapify(h)
print(h) # [1, 3, 2, 5, 9, 8]
print([heapq.heappop(h) for _ in range(len(h))]) # [1, 2, 3, 5, 8, 9]The outputs in the comments come from running this on Python 3.14.7. The exact internal arrangement is an observed result, not an API guarantee. Only the heap invariant and a smallest element at index 0 are guaranteed.
The list itself is not sorted, yet popping items one at a time returns them in ascending order. A min-heap guarantees that a smallest value is at index 0, while the heap invariant constrains only parent-child relationships.
The condition a heap keeps
The Python documentation defines a min-heap as a list where heap[k] <= heap[2*k+1] and heap[k] <= heap[2*k+2] for every k whose compared elements exist, counting elements from zero. Read the array as a binary tree and the children of index i are 2*i+1 and 2*i+2; its parent is (i-1)//2.
The public C++ working draft states the same relationship from the parent’s side: a range is a heap if comp(a[⌊(i−1)/2⌋], a[i]) is false for all 0 < i < N. The Python documentation points out that this zero-based form differs from the one-based formulas commonly used in textbooks.
Only parents and children are compared. Siblings, or nodes on different branches, have no required order. That is why index 1 can hold 3 while index 2 holds 2 in the output above: both are children of the root, 1. A sorted list always satisfies the condition, which is why the Python documentation notes that heap.sort() keeps the heap invariant.
Other languages don’t promise an iteration order either
The Java PriorityQueue documentation says that iterator() and spliterator() are not guaranteed to traverse elements in any particular order. If you need ordered traversal, it suggests Arrays.sort(pq.toArray()). The array from toArray() is in no particular order either. A for-each loop printing values out of order is not a bug.
In C++, std::priority_queue::top() returns the underlying container’s front(), and pop() is defined as pop_heap followed by pop_back. With the default comparator less, the heap condition becomes “a parent is not less than its child”, so the front holds the largest value. That is the opposite of Python’s heapq, which defaults to a min-heap. Python gained max-heap functions such as heapify_max and heappop_max in 3.14.
How it differs from a sorted list
To insert into a sorted list, you can find the position with binary search. The Python bisect documentation notes, however, that the O(log n) search is dominated by the O(n) insertion step.
Under the public C++ working draft, adding to a heap takes at most log N comparisons and removing the front at most 2 log N. The implementation note in the Java documentation likewise gives O(log n) for offer and poll, and constant time for peek. Finding an arbitrary element is another matter: Java’s contains and remove(Object) are linear. Turning an existing list into a heap with heapify runs in place in linear time.
If you need every value in order, sort. If values keep arriving and you repeatedly need only the smallest, use a heap. nsmallest, for when you only want the smallest few, works best for small n. The documentation says sorted() is more efficient for larger n and min() when n is 1.
Equal priorities
A heap does not keep equal values in the order they arrived. The Java documentation says that when several elements tie for least, the head is one of them, with ties broken arbitrarily. The Python documentation notes that a heapsort built on heapq, unlike sorted(), is not stable.
To preserve insertion order, store entries as [priority, count, task], as the Python documentation suggests. The count breaks ties. Since no two counts are equal, the tasks themselves are never compared.