priority if numbers in heap in python 3 [duplicate]

Question

Can someone explain me what's wrong in this code:

import heapq
a = [[1, 2], [0, 4], [3]]
h = []
for index in range(len(a)):
    i = 0
    while i < len(a[index]):
        heapq.heappush(h, a[index][i])
        i += 1
print(h)

I want to have smth like that: [0, 1, 2, 3, 4], but when I add 0 it's not becoming [0, 1, 2] but becoming [0, 2, 1].WHY? Thank you in advance!

Answer 1

What you're observing is intended behavior. Generally speaking, the top n values of a heap are not necessarily the smallest n values in the heap. (If this were true, we'd be able to sort in linear time by heapifying a list. But, heapifying a list is a linear-time operation, and comparison-based sorting requires O(n log n) time.)

To extract the smallest n elements, use heappop() n times:

import heapq
a = [[1, 2], [0, 4], [3]]
h = []
for index in range(len(a)):
    i = 0
    while i < len(a[index]):
        heapq.heappush(h, a[index][i])
        i += 1

n = 3
for i in range(n):
    print(heapq.heappop(h)) # Prints 0, 1, 2