Pythonによるヒープソート

2022.09.18

ヒープソートは、効率的なソートアルゴリズムのもう一つの例である。

その主な利点は、入力データに関係なく最悪実行時間が O(n*logn) と非常に短いことである。

その名前が示すように、ヒープソートはヒープデータ構造（優先度キューの一般的な実装）に大きく依存する。

ヒープソートは間違いなく最も単純なソートアルゴリズムの1つであり、他の単純な実装と比較してかなり効率的なアルゴリズムであるという事実と相まって、よく遭遇するアルゴリズムである。

ヒープソート

ヒープソートは、配列のヒープ部分から要素を一つずつ「取り除き」、配列のソート部分に追加することで動作します。

説明を進めてヒープデータ構造を再確認する前に、ヒープソート自体の属性について少し触れておこう。

つまり、必要なメモリは、その配列を格納するために必要なメモリ以外には、初期配列自体のサイズに依存しないのです。

例えば、元の配列のコピーは不要であり、再帰や再帰呼び出しスタックも存在しない。

ヒープソートの最も単純な実装では、通常、ソートされた値を格納するために2番目の配列が使用されます。

コード上ではより直感的で簡単なので、この方法を使うことになるが、完全にインプレースで実装することも可能である。

ヒープソートは不安定です。

つまり、同じ値を持つ要素の相対的な順序を維持することができません。

これはプリミティブな型（整数や文字など）では問題ないが、オブジェクトのような複雑な型をソートするときには問題になる。

例えば、age と name フィールドを持つカスタムクラス Person があり、そのクラスのオブジェクトが配列に格納されていて、その中には19歳の “Mike” と同じく19歳の “David” という人物がこの順で並んでいるとします。

もしこの配列を年齢順に並べ替えるとしたら、最初の配列では “Mike” と “David” が同じ順番で並んでいたとしても、並べ替え後の配列では “Mike” が “David” より前に現れるという保証はありません。

そうなる可能性はありますが、保証はありません。

ヒープソートは、Linuxカーネルで採用されているソートアルゴリズムです。

ヒープデータ構造

ヒープは、コンピュータサイエンスにおいて最も人気があり、頻繁に使用されるデータ構造の1つです。

もちろん、ソフトウェアエンジニアリングの面接で非常に人気があることは言うまでもありません。

ヒープは最小の要素(min-heap)を追跡しますが、同様に最大の要素(max-heap)を追跡するように簡単に実装することができます。

簡単に言えば、ミニヒープとは木ベースのデータ構造で、すべてのノードがすべての子ノードより小さいものである。

ほとんどの場合、二分木が使われる。

ヒープでは、 delete_minimum(), get_minimum(), add() の 3 つの操作をサポートしています。

ヒープの最初の要素を削除することだけが可能で、それ以降は「再ソート」されます。

ヒープは要素の追加や削除の後に「再ソート」され、最小の要素が常に最初の位置に来るようになります。

注意：これは決してヒープがソートされた配列であることを意味するものではありません。

すべてのノードがその子ノードよりも小さいという事実は、ヒープ全体が昇順であることを保証するのに十分ではありません。

ヒープの例を見てみましょう。

見てわかるように、上の例はヒープの説明に合っているが、ソートされてはいない。

この記事の主題ではないので、ヒープの実装の詳細には立ち入りません。

ヒープソートで使用するヒープデータ構造の重要な利点は、次に小さい要素が常にヒープの最初の要素であることです。

注：要素が取り除かれた後にヒープが要素をソートする方法のおかげで、配列をヒープにしたまま、次に小さい要素が最初の位置に移動する複雑さは、O（logn）時間かかり、これは非常に効率的な操作と言えます。

実装

配列の並べ替え

Python はヒープを生成して利用するためのメソッドを提供しているので、自分で実装する必要はありません。

  • heappush(list, item): ヒープに要素を追加し、その後、ヒープのまま再ソートします。空のリストでも利用できる。
  • heappop(list): 最初の(最小の)要素をポップアップ(削除)し、その要素を返します。この操作の後もヒープはヒープのままなので、heapify()を呼び出す必要はありません。
  • heapify(list): 与えられたリストをヒープに変換します。元の配列を変更したくないので、このメソッドを使用することはありませんが、このメソッドが存在することは注目に値します。

これで、ヒープソートの実装はかなり簡単になりました。

from heapq import heappop, heappush


def heap_sort(array):
    heap = []
    for element in array:
        heappush(heap, element)


ordered = []


# While we have elements left in the heap
    while heap:
        ordered.append(heappop(heap))


return ordered


array = [13, 21, 15, 5, 26, 4, 17, 18, 24, 2]
print(heap_sort(array))

出力。

[2, 4, 5, 13, 15, 17, 18, 21, 24, 26]

見ての通り、ヒープデータ構造を使えば、必要な要素を追加し、一つずつ削除していくだけで、重い仕事は終わりです。

これは、入力されたコインをその値によって並べ替えるコインカウント機のようなもので、後から取り出せばいいのです。

カスタムオブジェクトの並べ替え

カスタムクラスを使用する場合、事態は少し複雑になります。

通常、私たちのソートアルゴリズムを使用するために、クラス内の比較演算子をオーバーライドすることはお勧めしません。

しかし、我々の実装は組み込みのヒープメソッドに依存しているので、ここではそうすることができません。

Pythonは以下のメソッドを提供しています。

  • heapq.nlargest(*n*, *iterable*, *key=None*): iterable` で定義されたデータセットから、最大の n 個の要素を含むリストを返します。
  • heapq.nsmallest(*n*, *iterable*, *key=None*): iterable` で定義されたデータセットから、最小の n 個の要素を含むリストを返します。

これは単純に n = len(array) の最大/最小要素を取得するために利用できますが、このメソッド自身はヒープソートを使用しておらず、本質的には sorted() メソッドを呼び出すのと同じです。

カスタムクラスに対して残された唯一の解決策は、実際に比較演算子をオーバーライドすることです。

これは悲しいことに、1つのクラスにつき1種類の比較しかできないように制限されています。

この例では、Movie オブジェクトを年号でソートすることに制限されています。

しかし、カスタムクラスでヒープソートを使用するデモを行うことができます。

それでは、Movie クラスを定義してみましょう。

from heapq import heappop, heappush


class Movie:
    def __init__(self, title, year):
        self.title = title
        self.year = year


def __str__(self):
        return str.format("Title: {}, Year: {}", self.title, self.year)


def __lt__(self, other):
        return self.year < other.year


def __gt__(self, other):
        return other.__lt__(self)


def __eq__(self, other):
        return self.year == other.year


def __ne__(self, other):
        return not self.__eq__(other)

そして、 heap_sort() 関数を少し修正しましょう。

def heap_sort(array):
    heap = []
    for element in array:
        heappush(heap, element)


ordered = []


while heap:
        ordered.append(heappop(heap))


return ordered

そして最後に、いくつかのムービーをインスタンス化して配列に入れ、それらをソートしてみましょう。

movie1 = Movie("Citizen Kane", 1941)
movie2 = Movie("Back to the Future", 1985)
movie3 = Movie("Forrest Gump", 1994)
movie4 = Movie("The Silence of the Lambs", 1991);
movie5 = Movie("Gia", 1998)


array = [movie1, movie2, movie3, movie4, movie5]


for movie in heap_sort(array):
    print(movie)

出力です。

Title: Citizen Kane, Year: 1941
Title: Back to the Future, Year: 1985
Title: The Silence of the Lambs, Year: 1991
Title: Forrest Gump, Year: 1994
Title: Gia, Year: 1998

他のソートアルゴリズムとの比較

ヒープソートが、よく実装されたクイックソートに負けることが多いにもかかわらず、いまだによく使われている主な理由の1つは、その信頼性である。

ヒープソートの主な利点は、時間計算量に関するO(n*logn)の上限と、セキュリティに関するものである。

Linuxカーネルの開発者は、Quick SortではなくHeap Sortを使用する理由を以下のように説明している。

Heap Sortのソート時間は、平均値でも最悪値でもO(nlogn)である。

qsortは平均で約20%高速だが、O(nlogn)という最悪ケースでの挙動や余分なメモリ要件があり、カーネルでの使用には適さない。

さらに、クイックソートは予測可能な状況では挙動が悪く、内部実装の十分な知識があれば、O(n2)の悪い挙動を簡単に引き起こすことができるため、セキュリティリスク（主にDDoS攻撃）を引き起こす可能性がある。

ヒープソートがよく比較される別のアルゴリズムに、同じ時間複雑性を持つマージソートがある。

Merge Sortは安定しており、直感的に並列化できるという利点があるが、Heap Sortはそのどちらでもない。

ヒープソートは定数係数が大きいため、同じ複雑度であってもほとんどの場合マージソートより遅いということもある。

しかし、ヒープソートはマージソートよりもはるかに簡単にインプレースで実装できるため、メモリが速度よりも重要な要素である場合にはヒープソートが推奨される。

結論

ヒープソートは他の効率的な汎用アルゴリズムほど有名ではありませんが、その予測可能な動作（不安定であることを除く）により、メモリやセキュリティが少しでも速い実行時間よりも重要な場合に使用するには素晴らしいアルゴリズムです。

Pythonの組み込み機能を利用すれば、コインカウンターのように、アイテムをヒープに置いて取り出すだけで、直感的に実装することができます。

タイトルとURLをコピーしました