Photo by Fineas Anton

ヒープソート

概要

ここで神のごとくわかりやすい、 わくわくアカデミーの動画を引用させていただきます。 動画を見ると、だいたいの雰囲気が掴みやすいかなと思います。

コード

簡単なもの

標準ライブラリ heapq (opens new window) を使えば、とても簡単に実装できます。 heapq については 二分ヒープ で解説させていただきました。

from heapq import heappush
from heapq import heappop

def linked_heap_sort(lst):
    heap = []
    while lst:
        heappush(heap, lst.pop())
    while heap:
        lst.append(heappop(heap))


lst = [3333, 5123, 9981, 1243, 7412]
linked_heap_sort(lst)
print(lst)
# [1243, 3333, 5123, 7412, 9981]

難しいもの

heapq のコード heapq.py (opens new window) を コピペして一部書き換えています。

def heap_sort(lst):
    # 1) ヒープ heap を作成
    heapify(lst)
    
    # 2) 先頭を取り出し末尾と取り替え
    index = len(lst) - 1
    while index:
        lst[0], lst[index] = lst[index], lst[0]
        _siftup(lst, 0, index)
        index = index - 1

    # 3) 逆さまなので反転
    lst.reverse()


#
# heapq.py
#
def _siftdown(heap, startpos, pos):
    newitem = heap[pos]
    while pos > startpos:
        parentpos = (pos - 1) >> 1
        parent = heap[parentpos]
        if newitem < parent:
            heap[pos] = parent
            pos = parentpos
            continue
        break
    heap[pos] = newitem


# heapq._siftup を
# 先頭の２行だけを書き換えました。
#
# - def _siftup(heap, pos):
# -     endpos = len(heap)
# + def _siftup(heap, pos, endpos):
# +     # endpos = len(heap)
#
def _siftup(heap, pos, endpos):
    startpos = pos
    newitem = heap[pos]
    childpos = 2 * pos + 1
    while childpos < endpos:
        rightpos = childpos + 1
        if rightpos < endpos and not heap[childpos] < heap[rightpos]:
            childpos = rightpos
        heap[pos] = heap[childpos]
        pos = childpos
        childpos = 2 * pos + 1
    heap[pos] = newitem
    _siftdown(heap, startpos, pos)


# heapq._heapify を
# 書き換え
#
# - _siftup(x, i)
# + _siftup(x, i, n)
#
def heapify(x):
    n = len(x)
    for i in reversed(range(n // 2)):
        _siftup(x, i, n)


lst = [3333, 5123, 9981, 1243, 7412]
heap_sort(lst)
print(lst)
# [1243, 3333, 5123, 7412, 9981]

途中結果を表示する。

ヒープとは、ざっくり言えば上より下が大きい木です。 クイックソート、マージソートは難しい方の実装の途中結果を表示しましたが、 ここでは簡単な方の実装の途中結果を表示します。

heapify の動作を表示してしまうと、ごちゃごちゃしてしまうので避けました。 ここでは heappush で詰め込んで heappop で取り出している、 ということだけなんとなく伝わればと思っています。

heapify, heappush, heappop の実装と動作については 二分ヒープ でご紹介させていただきました。

ヒープソートについては、表示が少し大掛かりになるので、 表示させてみる場合は GitHub からのダウンロードをお願いいたします。

git clone https://github.com/niconico25/sort
cd sort

# ヒープを表示するために使います
git clone https://github.com/niconico25/tree
python3 linked_heap.py

$ python3 linked_heap.py 
# リストの末尾から１つずつ要素を取り出し
# ヒープを作ります。
43 28 96 31  9 50  8




    前半のこの箇所を表示しています。
    while lst:
        heappush(heap, lst.pop())

[43, 28, 96, 31, 9, 50]
08

[43, 28, 96, 31, 9]
  08  
50    

[43, 28, 96, 31]
  08  
50  09

[43, 28, 96]
      08      
  31      09  
50            

[43, 28]
      08      
  31      09  
50  96        

[43]
      08      
  31      09  
50  96  28    

[]
      08      
  31      09  
50  96  28  43

#
# ヒープが完成しました！
#   どこの要素を見ても、
#   上より下が大きいです。
#




    ここからは
    後半のこの箇所を表示しています。
    while heap:
        lst.append(heappop(heap))

# あとはヒープから
# １つずつ取り出していけば
# ソートの完成です。
[8]
      09      
  31      28  
50  96  43    

[8, 9]
      28      
  31      43  
50  96        

[8, 9, 28]
      31      
  50      43  
96            

[8, 9, 28, 31]
  43  
50  96

[8, 9, 28, 31, 43]
  50  
96    

[8, 9, 28, 31, 43, 50]
96

[8, 9, 28, 31, 43, 50, 96]



 8  9 28 31 43 50 96
$

おわりに

最後にすこしだけメモリ使用量に触れました。 各アルゴリズムのメモリ使用量の一覧は Wikipedia にあります。

• ソート - Wikipedia (opens new window)