リストの要素をヒープ順で並び替える

Question

前提・実現したいこと

pythonチュートリアルにて、コードを複写しているのですが、heapqモジュールのヒープ順に並び替えるという内容が理解できず、webサイトなどで調べたのですが解決できない状態です。

該当のソースコード

from heapq import heapify, heappop, heappush
data = [1,3,5,7,9,2,4,6,8,0]
heapify(data)
print(data)
#出力結果：[0, 1, 2, 6, 3, 5, 4, 7, 8, 9]
#疑問：なぜこの配列になるか分からない

Answer 1

       1
   3       5
 7   9   2   4
6 8 0

       0
   1       2
 6   3   5   4
7 8 9

元のリスト [1,3,5,7,9,2,4,6,8,0] を 2分木とすると、1 の子が 3 と 5、
3 の子が 7 と 9、5 の子が 2 と 4、7 の子が 6 と 8、9 の子が 0 です。

これは、子が親より小さいところがあるので、ヒープ構造ではありません。

0 を親と交換しながら上にあげていきます。6 や 2 も上にあげます。
これで、御覧のようなヒープが完成しました。
リストにすると、[0,1,2,6,3,5,4,7,8,9] です。

Comments

[pythonsyosinsya]

理解できました。ありがとうございました！