CODEWITHSUNDEEP
pythonheap
Arpit-Gole
Arpit-Gole

Reputation: 385

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

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=' ')

Upvotes: 4

Views: 579

Answers (2)

kaya3
kaya3

Reputation: 51034

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.

Upvotes: 1

shx2
shx2

Reputation: 64318

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.

Upvotes: 7

Related Questions