heappush() and heapify() gives different output for same input in python when using heapq, error?

Question

import heapq

heap = []   # creates an empty heap
item = [20, 4, 8, 10, 5, 7, 6, 2, 9]
for i in item:
    heapq.heappush(heap, i)  # pushes a new item on the heap

print('Heap obtained from heappush() : ', heap)

same_item = [20, 4, 8, 10, 5, 7, 6, 2, 9]
heapq.heapify(same_item)  # transforms list into a heap, in-place, in linear time

print('Heap obtained from heapify() : ', same_item)

My understanding is both heappush() and heapify() should give the same output whereas output says otherwise.

Heap obtained from heappush() :  [2, 4, 6, 5, 10, 8, 7, 20, 9]
Heap obtained from heapify() :  [2, 4, 6, 9, 5, 7, 8, 10, 20]

Thank you in advance.

Edited: Thanks to @shx2's answer as I was able to verify the correct functionality. Code to verify.

print('\nPopping elements 1 by 1 to very the real structure obtained from heappush() and heapify()\n')

print('First from heap obtained from heappush() : ', end='')
for i in range(len(item)):
    print(heapq.heappop(heap), end=' ')

print('\nNow from heap obtained from heapify() : ', end='')
for i in range(len(item)):
    print(heapq.heappop(same_item), end=' ')

shx2 · Answer 1 · 2020-08-12T12:05:36.533

7

Not an error. Both produce valid heaps.

Heaps are binary trees for which every parent node has a value less than or equal to any of its children.

This ordering is not uniquely defined.

In other words, a heap is not a sorted structure, so there are many different orderings which form valid heaps.

To verify, run a heappop-loop on both, and check they both return the items in sorted order.

edited Aug 12 '20 at 12:05

answered Aug 12 '20 at 12:00

shx2

61,779
13
130
153

Thank you @shx2 whereas don't you think the way I was printing the heap list should also reflect the same i.e should show the sorted list. – Arpit-Gole Aug 12 '20 at 12:25
@Arpit-Gole In both cases the list isn't sorted. Also, think about it as internal private representation. There are many different alternative internal representations. – shx2 Aug 14 '20 at 04:50

score 1 · Answer 2 · answered Aug 12 '20 at 12:07

To add to @shx2's answer, the heapify function does not work by doing heappush for each item; it uses a different, more efficient algorithm. The heappush function takes O(log n) time, so doing it n times would take O(n log n) time, but the heapify algorithm actually works in O(n) time.

The algorithm for building a heap in linear time is described in this other Stack Overflow Q&A.

heappush() and heapify() gives different output for same input in python when using heapq, error?

2 Answers2