heap order in python

Question

New to heap data structure.

Trying to create a heap from a list.

li = [5, 7, 9, 1, 3]

heapq.heapify(li)

After heapity, the output is

[1, 3, 9, 7, 5]

Why this order?
I thought that for a min-priority heap, the elements should be ordered from min to max, i.e.
heapq.heapify(li) should be the same as li.sort()

Could someone help me understand?

There can be multiple ways to make a list into a heap, see [here](https://stackoverflow.com/questions/30552777/when-building-heap-is-heap-unique). — hilberts_drinking_problem, May 31 '18 at 14:33
Possible duplicate of [What is Python's heapq module?](https://stackoverflow.com/questions/19979518/what-is-pythons-heapq-module) — Norrius, May 31 '18 at 14:34
The heaps in `heapq` are a kind of binary tree. Every parent`heap[k]` has children at `heap[2*k+1]` and `heap[2*k+2]`. Every parent is less than or equal to its children. Read up on the [heap data structure](https://en.wikipedia.org/wiki/Heap_(data_structure)) in general before becoming familiar with the python implementation. — Patrick Haugh, May 31 '18 at 14:35

score 5 · Accepted Answer · answered May 31 '18 at 14:41

heaps are not in fact sorted in the same way lists are sorted. Python does not have a unique heap data structure, and uses lists with heap operations which is probably the source of some of you confusion. A sorted (minimum priority) heap is one that satisfies the "heap condition" such that any child node is greater than its parent. This does not imply that the flattened representation will be in order.

your example would look like this before flattening:

Each node gets up to 2 children, and children are always added left to right until the row is full. The flat representation is then created by concatenating the rows: [1] + [3, 9] + [7, 5]

chepner · Answer 2 · 2018-05-31T15:26:11.940

It's easier to look at a heap as a tree:

         1
     3      9
  7     5

where each node is less than either of its children, but the order of the children is irrelevant (which distinguishes a heap from a binary search tree).

A complete tree admits a simple embedding in an array by numbering the nodes in breadth-first order, starting with the root as node 1.

         1(1)
     3(2)      9(3)
  7(4)     5(5)

With such an embedding, the following relations hold:

li[i] <= li[2*i]
li[i] <= li[2*i + 1]

2*i and 2*i + 1 are the formulas for computing the left and right child, respectively, of the node at position i:

 +--+--+
 |  v  v
[1, 3, 9, 7, 5]
    |     ^  ^
    +-----+--+

(You can specify these properties for a 0-based array, but it's simpler to think about with 1-based arrays.)

Such a list is heap-ordered (which is weaker than being sorted, as all sorted lists are also heap-ordered), and allows the standard heap methods to be implemented efficiently.

*Such a list is heap-ordered, which is different from sorted* — I'd also note that the usual sort implies heap-ordering, but not the other way round. — Norrius, May 31 '18 at 15:17

score 1 · Answer 3 · answered May 31 '18 at 14:41

in fact heap sort is a Half-arranged algorithm. main idea is every parent should be smaller or equal to its children(in min heap sort). so we know the first element is smallest. when we pop the first element of a heap, the next smallest element will take its place.
For more information see these liks:

heap sort
wikipedia

heap order in python

3 Answers3