ヒープソート（Pythonによるアルゴリズムとデータ構造）

本記事は、ソフトバンクパブリッシングから発行されている「定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)」を参考にPythonでアルゴリズムとデータ構造について学習していきます。

今回は、半順序木を利用したヒープソート（Heap Sort）について学んでいきます。

半順序木とは
ヒープとは
Pythonでヒープソートを実装してみる
動作確認
参考書籍

半順序木とは

前回では、基本的なデータ構造として待ち行列（キュー）について学びました。

ネットワークの世界では、ソケットでキューが使われていますが、通信の中でも重要度の高いパケットなどに優先度を付与することができます。

このような待ち行列の仕組みを優先順位付き待ち行列（Priority Queue）と言います。

そして、この仕組みを実現するためのデータ構造として半順序木（Partial Ordered Tree）があります。

半順序木では以下のような条件を満たします。

親の値は子の値よりも小さい、もしくは等しい

以下が半順序木を示したものになります。

上記から半順序木では、最小の値が常に根になります。

また根から葉までの高さの差を1以内にした平衡木であり、要素の挿入には最下段の左から値を挿入していきます。

ヒープとは

ヒープ（Heap）は２つの異なる意味を持っています。

一つは、メモリ領域としてのヒープです。

C言語の標準ライブラリではmalloc()でヒープ領域から動的にメモリを割り当て、free()でそのメモリ領域を解放します。

もう一つは、今回利用する半順序木を配列を使って実現したデータ構造としてのヒープです。

上記のfig1をヒープで表現すると以下のようになります。

上記からヒープはインデックス（添え字）を1から使用し、0は使用しません。

またある節のインデックスを $i$ とすると、その子は $2i$ と $2i+1$ になります。

Pythonでヒープソートを実装してみる

それでは、Pythonでヒープソートを実装してみます。

# heap_sort.py
import time
import pickle

class Heap:
    def __init__(self, size):
        self.heap = [None for _ in range(size+1)]
        self.max_size = size + 1
        self.size = 0

    def downheap(self, src, dst):
        value = self.heap[src]
        i = src
        while i <= int(dst / 2):
            j = i * 2
            if j+1 <= dst and self.heap[j] < self.heap[j+1]:
                j += 1
            if value >= self.heap[j]:
                break
            self.heap[i] = self.heap[j]
            i = j
        self.heap[i] = value

    def deletemin(self):
        if self.size < 1:
            print("Heap is empty.")
            return
        value = self.heap[1]
        self.heap[1] = self.heap[self.size]
        self.size -= 1

        self.downheap(1, self.size)
        return value

    def upheap(self, size):
        value = self.heap[size]
        while size > 1 and self.heap[int(size/2)] < value:
            self.heap[size] = self.heap[int(size/2)]
            size = int(size/2)
        self.heap[size] = value

    def insert(self, value):
        if self.size >= self.max_size:
            print("heap is overflow.")
            return
        self.size += 1
        self.heap[self.size] = value
        self.upheap(self.size)

    def heap_sort(self):
        for i in range(self.size, 1, -1):
            tmp = self.heap[1]
            self.heap[1] = self.heap[i]
            self.heap[i] = tmp
            self.downheap(1, i-1)


with open('sample_data.pkl', 'rb') as f:
    lst = pickle.load(f)

h = Heap(len(lst))
for i in lst:
    h.insert(i)
start = time.time()
h.heap_sort()
print("elapsed {} sec".format(time.time() - start))

上記ではデータが昇順になるようにしています。

降順になるようにするには、upheap()とdownheap()の大小比較を逆にするだけで実現できます。

動作確認

それでは上記で作成したスクリプトを実行してみます。

事前に1~20,000までの値からランダムに20,000個生成したリストをpickleデータとして保存しておき、これをロードします。

自環境で実行した結果を以下にまとめます。

**データ20,000個を整列した結果一覧**
アルゴリズム名	所要時間（秒）
Python 組込みメソッド（sort()）	0.015
Bubble Sort	72.979
Selection Sort	17.747
Insertion Sort	41.236
Shell Sort	0.253
Quick Sort	0.084
Merge Sort(List)	0.168
Merge Sort(Linked List)	0.092
Heap Sort	0.233