Why cant I create heap out of python list

Question

import heapq
x=[1,4,2]
heapq.heapify(x)
print(x)

The result I get is [1,4,2], what am I missing?

Answer 1

There is no special heap data structure in Python. A heap is just a list for which the "heap invariant" holds, i.e.

Heaps are arrays for which a[k] <= a[2*k+1] and a[k] <= a[2*k+2] for all k, counting elements from 0. For the sake of comparison, non-existing elements are considered to be infinite. The interesting property of a heap is that a[0] is always its smallest element.

As long as this holds (which heapify ensures), heappop can quickly pop the smallest element and replace it with the next-smallest. In the case of your list, the heap invariant was already fulfilled, despite the list not being fully sorted, so heapify did not change anything. Still, if you heappop the elements, they will come out in sorted order.