今回は、Max Heap（Pythonではヒープキューと呼ばれています）について詳しく説明します。
Python のヒープとそのライブラリ関数(heapq モジュール)についてはすでに学びました。
ここでは、max heap とその実装について学び、max-heap 用の heapify, heappush, heappop 関数を実装する Python コードを見てみましょう。
マックスヒープとは？
マックスヒープは完全な二分木です (完全な二分木とは、最深部/最終レベルの右端のノードを除いて完全に埋まっている木のことです) その中で各ノードはそのすべての子より大きいか等しいです。
したがって、ヒープのルート・ノードが最大の要素です。
ヒープデータ構造は一般に優先度待ち行列を表すのに用いられ、最大ヒープは最大要素を最高優先度とする優先度待ち行列と理解することができる。
import sys
#defining a class max_heap for the heap data structureclass max_heap:
def __init__(self, sizelimit):
self.sizelimit = sizelimit
self.cur_size = 0
self.Heap = [0]*(self.sizelimit + 1)
self.Heap[0] = sys.maxsize
self.root = 1
# helper function to swap the two given nodes of the heap
# this function will be needed for max-heapify and insertion
# in order to swap nodes which are not in order (not satisfy max-heap property)
def swapnodes(self, node1, node2):
self.Heap[node1], self.Heap[node2] = self.Heap[node2], self.Heap[node1]
# THE MAX_HEAPIFY FUNCTION
def max_heapify(self, i):
# If the node is a not a leaf node and is lesser than any of its child
if not (i >= (self.cur_size//2) and i <= self.cur_size):
if (self.Heap[i] < self.Heap[2 * i] or self.Heap[i] < self.Heap[(2 * i) + 1]):
if self.Heap[2 * i] > self.Heap[(2 * i) + 1]:
# Swap the node with the left child and call the max_heapify function on it
self.swapnodes(i, 2 * i)
self.max_heapify(2 * i)
else:
# Swap the node with right child and then call the max_heapify function on it
self.swapnodes(i, (2 * i) + 1)
self.max_heapify((2 * i) + 1)
# THE HEAPPUSH FUNCTION
def heappush(self, element):
if self.cur_size >= self.sizelimit :
return
self.cur_size+= 1
self.Heap[self.cur_size] = element
current = self.cur_size
while self.Heap[current] > self.Heap[current//2]:
self.swapnodes(current, current//2)
current = current//2
# THE HEAPPOP FUNCTION
def heappop(self):
last = self.Heap[self.root]
self.Heap[self.root] = self.Heap[self.cur_size]
self.cur_size -= 1
self.max_heapify(self.root)
return last
# THE BUILD_HEAP FUNCTION
def build_heap(self):
for i in range(self.cur_size//2, 0, -1):
self.max_heapify(i)
# helper function to print the heap
def print_heap(self):
for i in range(1, (self.cur_size//2)+1):
print("Parent Node is "+ str(self.Heap[i])+" Left Child is "+ str(self.Heap[2 * i]) + " Right Child is "+ str(self.Heap[2 * i + 1]))
maxHeap = max_heap(10)
maxHeap.heappush(15)
maxHeap.heappush(7)
maxHeap.heappush(9)
maxHeap.heappush(4)
maxHeap.heappush(13)
maxHeap.print_heap() |
Understanding the functions for implementing max heap
1. max-heapify 関数
この関数は、ノードとその全ての子孫（子ノードとその子）を、max-heap 特性に従わせる。
まず、与えられたノードとそのすべての子ノードのうち、最大の値を持つノードを見つける。
次に、与えられたノード（i）と見つかった最大値のノード（j）を交換し、ノードjに対して（再帰的に） max-heapify関数を呼び、ノードjに割り当てられた新しい値がそのサブツリーの最大ヒープ特性を破らないことを確認します。
最大でも木の深さまでトラバースする必要があるので、その時間複雑度はO(d)、dは深さ、または、ノード数の観点からはO(log n)、nはヒープ内の要素数です。
2. ビルドヒープ関数
この関数は、任意のリスト（または他の任意のイテレート可能なもの）からヒープを構築します。
つまり、リストを受け取り、max-heapプロパティを満たすように各要素を並べ替えます。
これは、単純に各ノードに対して max-heapify を繰り返し適用することで実装することができます。
この関数の時間計算量は O(n) となる。
3. ヒープポップ関数
この関数はヒープの最大値(ルート要素)をポップアウトさせる。
これは実際には、ルートノードと最後のノードをスワップし、（現在の最大値を含む）現在の最後のノードを削除し、スワップによる変更後もヒープ特性を維持するように、ルートノードに対して max-heapify を呼び出すことによって行われます。
子孫を処理するだけなので、時間計算量は O(log n) (nは要素数)、または O(h) (hは木の高さ) であり、完全木なので log n となります。
4. heappush関数
この関数は、新しい要素をヒープにプッシュし、ヒープのプロパティを維持したまま、正しい位置に配置します。
これは実際にはヒープの末尾に新しいノードを追加することで行われます。
ここで、ヒープ特性を維持するために、最後のノードから上にトラバースして (必要ならスワップして)、プッシュされた要素の追加により違反する可能性のあるヒープ特性を修正します。
heappop` と同様に、サブツリーの高さをトラバースするだけなので、ここでの時間計算量は O(log n) となります。
5. extractMax 関数
この関数はヒープから最も優先度の高い要素（ルート要素または最大要素）を返します。
ヒープに変更を加えずルートの値を返すだけでよく、ルートには O(1) 時間でアクセスできるので、この関数の時間計算量は O(1) となる。
Max Heap の完全な Python 実装
では、Python でマックスヒープを実装してみましょう。
コードではリスト [15, 7, 9, 4, 13] を使い、build-heap関数を使ってマックスヒープに変換しています。
作られたヒープは次のようになります。
Parent Node is 15 Left Child is 13 Right Child is 9
Parent Node is 13 Left Child is 4 Right Child is 7
|
実装は以下の通りです。
結果は以下の通りです。
出力は、画像例で示したイラストから確認できます。
まとめ
この記事では、max-heapについて学びました。
max-heapify,heappush,heappop,build_heap` の各関数がどのように動作するのかを学びました。
さらに、これらの関数をゼロからPythonで実装しました。
今後も有益な記事を期待しています。
ハッピーラーニング!