Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

Tags:

python

heap

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=' ')
like image 660
Arpit-Gole Avatar asked Sep 18 '25 17:09

Arpit-Gole


1 Answers

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.

like image 112
shx2 Avatar answered Sep 21 '25 08:09

shx2