今回は、Min Heap（Pythonではヒープキューと呼ばれています）について詳しく説明します。
Pythonのヒープとそのライブラリ関数(heapqモジュール)については既に学びました。
ここでは、ミニヒープとその実装について学び、さらに heapify, heappush, heappop 関数を自分自身で実装するための Python コードを見ていきます。
簡単に復習しておきましょう。
この記事もチェック：PythonのOshashモジュールを使ってハッシュ関数を実装する方法
Minヒープとは？
最小ヒープとは、完全な二分木（完全な二分木とは、最深部/最終レベルの右端ノードを除いて完全に埋まっている木）であり、各ノードはそのすべての子より小さいか等しくなっています。
したがって、ヒープのルートノードは最小の要素です。
ミニヒープのデータ構造は、一般に優先度待ち行列を表現するのに使われる。
import sys
#defining a class min_heap for the heap data structureclass min_heap:
def __init__(self, sizelimit):
self.sizelimit = sizelimit
self.cur_size = 0
self.Heap = [0]*(self.sizelimit + 1)
self.Heap[0] = sys.maxsize * -1
self.root = 1
# helper function to swap the two given nodes of the heap
# this function will be needed for heapify and insertion to swap nodes not in order
def swapnodes(self, node1, node2):
self.Heap[node1], self.Heap[node2] = self.Heap[node2], self.Heap[node1]
# THE MIN_HEAPIFY FUNCTION
def min_heapify(self, i):
# If the node is a not a leaf node and is greater 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 then call the min_heapify function on it
self.swapnodes(i, 2 * i)
self.min_heapify(2 * i)
else:
# Swap the node with right child and then call the min_heapify function on it
self.swapnodes(i, (2 * i) + 1)
self.min_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.min_heapify(self.root)
return last
# THE BUILD_HEAP FUNCTION
def build_heap(self):
for i in range(self.cur_size//2, 0, -1):
self.min_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]))
# Driver CodeminHeap = min_heap(10)
minHeap.heappush(15)
minHeap.heappush(7)
minHeap.heappush(9)
minHeap.heappush(4)
minHeap.heappush(13)
minHeap.print_heap() |
H
Understanding the functions used in the implementation of Min Heap
1. min-heapify 関数
この関数は、あるノードとそのすべての子孫ノード（子ノードとその子）を ヒープ属性に従わせる。
ヒープの性質に従い、与えられたヒープがその部分木の最小ノードになるように、ノードをスワップして並べ替えます。
この関数は、まず、与えられたノードとその子供のうち、最も小さい値を持つノードを見つける。
そして、与えられたノード（iとする）を、見つかった最小値のノード（jとする）と交換し、ノードjに対して（再帰的に）min-heapify関数を呼び出す。
これにより、ノードjに割り当てられた新しい値が、その部分木のヒープ特性を破らないことが確認される。
この関数は、せいぜい木の深さまで走査しなければならないので、その時間計算量はO(d)(dは深さ、ノード数でいえばO(log n)、nはヒープ内の要素数)です。
2. ビルドヒープ関数
この関数は、任意のリスト（または他の任意の反復可能ファイル）からヒープを構築 します。
すなわち、リストを受け取り、ヒープ特性を満たすように各要素を並べ替 える。
これは、各ノードに対してmin-heapifyを繰り返し適用することにより、単純に実装することができます。
この関数の時間計算量はO(n)であり、ここでnはヒープ内の要素数です。
3. ヒープポップ関数
この関数はヒープの最小値(ルート要素)をポップアウトします。
これは実際には、ルートノードと最後のノードを交換し、（最小値を含む）最後のノードを削除し、スワップによる変更後もヒープ特性を維持するように、ルートノードに対してmin-heapifyを呼び出すことによって行われる。
子孫を処理するだけなので、時間計算量はO(log n)（nは要素数）、またはO(h)（hは木の高さ）で、完全木であるためlog nとなります。
4. heappush関数
この関数は、新しい要素をヒープにプッシュし、ヒープのプロパティを維持したまま、正しい位置に配置します。
これは実際にはヒープの末尾に新しいノードを追加することで行われます。
さて、ヒープ特性を維持するために、最後のノードから上にトラバースし（必要に応じてスワップし）、違反している可能性のあるヒープ特性を修正します。
heappopと同様に、サブツリーの高さをトラバースするだけなので、ここでの時間複雑性はO(log n)です。
5. extractMin関数
この関数はヒープから最も優先度の高いもの（ルート要素）を返す。
ルートの値を返すだけでヒープに変更を加えず、ルートには O(1) 時間でアクセスできるので、この関数の時間複雑度は O(1) となります。
Min Heap データ構造の完全な Python 実装
以下は、PythonでMin Heapを実装するための完全なプログラムです。
Parent Node is 4 Left Child is 7 Right Child is 9
Parent Node is 7 Left Child is 15 Right Child is 13
|
出力。
コクルージョン
この記事では、min heapについて学びました。
heapify、heappush、heappop`の関数がどのように動作するのかを勉強した。
さらに、pythonでゼロからmin heapのデータ構造を実装しました。
今後も有益な記事を期待しています。