python实现⼆叉堆中的⼤顶堆（⼤根堆）
堆（英语：heap)是计算机科学中⼀类特殊的数据结构的统称。堆通常是⼀个可以被看做⼀棵树的数组对象。堆总是满⾜下列性质：
堆中某个节点的值总是不⼤于或不⼩于其⽗节点的值；
堆总是⼀棵完全⼆叉树。
将根节点最⼤的堆叫做最⼤堆或⼤根堆，根节点最⼩的堆叫做最⼩堆或⼩根堆。常见的堆有⼆叉堆、斐波那契堆等。他们的时间复杂度如下：
Operation find-max delete-max insert decrease-key merge
BinaryΘ(1)Θ(log n)O(log n)O(log n)Θ(n)
FibonacciΘ(1)O(log n)Θ(1)Θ(1)Θ(1)
class BigPq(object):
def__init__(self, arr: list):
self.arr = arr
self.mark = 1
while self.mark == 1:
self.build()
def build(self):
self.mark = 0  # 先置为零，只要经过⼀次swap函数，就再次置为1
index = len(self.arr) - 1
for i in range(index):
if i * 2 + 2 <= index:  # 如果左右两个⼦节点都存在，去⽐较他们的⼤⼩
elif i * 2 + 1 <= index:  # 如果只有左⼦节点存在，去⽐较他们的⼤⼩
if self.arr[i] < self.arr[i * 2 + 1]:
self.swap(i, i * 2 + 1)
else:
break
def tri(self, head: int, left: int, right: int):
if self.arr[head] < self.arr[left]:
self.swap(head, left)
if self.arr[head] < self.arr[right]:
self.swap(head, right)
def swap(self, index_1: int, index_2: int):
self.mark = 1
temp = self.arr[index_2]
self.arr[index_2] = self.arr[index_1]
self.arr[index_1] = temp
def show(self):
print(self.arr)
def pop(self) -> int:
self.arr[0] = self.arr[-1]
temp = self.arr.pop()
self.mark = 1
while self.mark == 1:
self.build()
return temp
def push(self, value: int):
self.arr.append(value)
self.mark = 1
while self.mark == 1:
二叉树的遍历pythonself.build()

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。