5
python实现小顶堆MinHeap和哈夫曼树HaffumanTree
source link: https://blog.csdn.net/qq_45592128/article/details/112056978
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
python实现小顶堆MinHeap和哈夫曼树HaffumanTree
堆是一种非线性结构,可以被视作数组,也可以被视作完全二叉树
堆就是利用完全二叉树的结构来维护的一维数组
大顶堆:每个结点的值都大于或等于其左右孩子结点的值
小顶堆:每个结点的值都小于或等于其左右孩子结点的值
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,这是正确的。
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK