小頂堆
堆是一種非線性結構，可以被視作陣列，也可以被視作完全二叉樹
堆就是利用完全二叉樹的結構來維護的一維陣列
大頂堆：每個結點的值都大于或等于其左右孩子結點的值
小頂堆：每個結點的值都小于或等于其左右孩子結點的值
class MinHeap:
def __init__(self):
self.__values: list = []
def __swap(self, i, j):
self.__values[int(i)], self.__values[int(j)] = self.__values[int(j)], self.__values[int(i)]
def push(self, data):
self.__values.append(data)
i = len(self.__values) - 1
while i != 0 and self.__values[int(i)] < self.__values[int((i - 1) / 2)]:
self.__swap(i, (i - 1) / 2)
i -= 1
i /= 2
def top(self):
if len(self.__values) == 0: return None
return self.__values[0]
def pop(self):
top = self.__values[0]
self.__swap(0, len(self.__values) - 1)
self.__values.pop()
i = 0
while True:
left = 2 * i + 1
right = 2 * i + 2
max_ = i
if left < len(self.__values) and self.__values[left] < self.__values[max_]: max_ = left
if right < len(self.__values) and self.__values[right] < self.__values[max_]: max_ = right
if max_ == i: break
self.__swap(i, max_)
i = max_
return top
def isEmpty(self):
return len(self.__values) == 0
def __len__(self):
return len(self.__values)
@staticmethod
def fromList(dataList: list):
heap = MinHeap()
for i in dataList:
heap.push(i)
return heap
哈夫曼樹
現在讓我使用小頂堆來構造一顆哈夫曼樹,并輸出它的WPL(帶權路徑長度), 首先我們需要一個哈夫曼樹類
class HaffumanTree:
class Node:
def __init__(self, value, left=None, right=None):
self.value = value
self.left: HaffumanTree.Node = left
self.right: HaffumanTree.Node = left
def __lt__(self, other) -> bool:
return self.value < other.value
def __gt__(self, other):
return self.value > other.value
def __init__(self, datas: list):
self.__root: HaffumanTree.Node = None
self.__WPL: int = 0
minHeap = MinHeap()
for item in datas:
minHeap.push(HaffumanTree.Node(item))
while len(minHeap) != 1:
# 貪婪
# 每次把最小的兩個結點取出來然后合并成一個大結點并加入小頂堆,當堆中只剩一個結點時,這個結點就是哈夫曼樹的根節點
left = minHeap.pop()
right = minHeap.pop()
minHeap.push(HaffumanTree.Node(left.value + right.value, left, right))
# 計算帶權路徑長度
self.__WPL += left.value + right.value
self.__root = minHeap.top()
def WPL(self):
return self.__WPL
測驗
def main():
print(HaffumanTree([2, 1, 4, 5, 7, 3, 4, 9]).WPL())
最后輸出98，這是正確的，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/243590.html
標籤：python
上一篇：雜談：經典演算法之亂數生成