"""
堆的相关操作:
1,从最后到头逐个调整元素
2,取出堆定的那个需要的元素
3,将最后一个元素放到堆顶,然后逐个交换完成堆的调整
4,插入元素时,直接插入末尾,然后调整真个堆
这里以最小堆为例子,其实就是优先队列
"""
class Heap:
def __init__(self, data):
self.data = data
self.length = len(data)
self.init_heap()
# 初始化调整个堆的结构
def init_heap(self):
# 从最后一个元素开始调整
for i in range(self.length-1, -1, -1):
# 找到他的根节点
if i % 2 == 0:
root_index = i//2-1
else:
root_index = i//2
if root_index >= 0:
# print('找到根节点:', root_index)
# print(i, root_index)
if self.data[root_index] > self.data[i]: # 不符合顶堆的定义就交换
self.data[root_index], self.data[i] = self.data[i], self.data[root_index]
self.deal_all_sons(i) # 一旦发生交换,就可能会让该堆不符合堆的定义
return
def deal_all_sons(self, i):
# 从堆顶往堆左右两端的元素调整
# 左节点
left_index = i*2+1
# 右节点
right_index = (i+1) * 2
# 子堆定点和左节点相比较
if left_index <= self.length-1 and self.data[i] > self.data[left_index]:
self.data[i], self.data[left_index] = self.data[left_index], self.data[i]
self.deal_all_sons(left_index) # 递归调整所有的节点
# 子堆定点和右节点相比较
if right_index <= self.length - 1 and self.data[i] > self.data[right_index]:
self.data[i], self.data[right_index] = self.data[right_index], self.data[i]
self.deal_all_sons(right_index) # 递归调整所有的节点
# 取出堆顶的一个元素
def get_one(self):
if self.length < 1:
print('序列的长度不足!')
ret = self.data[0]
# 将堆尾的那个元素放到堆顶
self.data[0] = self.data[self.length-1]
# 删除堆尾的位置
del self.data[self.length-1]
self.length -= 1
# 调整整个堆
self.deal_all_sons(0)
return ret
# 向堆中插入一个元素
def insert(self, x):
self.data.append(x)
self.length += 1
self.init_heap() # 重新调整整个堆
def main():
n = 10
# list_data = [0] * n
list_data = [66, 5, 52, 12, 51, 53, 26, 70, 92, 85]
# for i in range(n):
# list_data[i] = rd.randint(1, 100)
print('获得的初始数据:', list_data)
heap = Heap(list_data[0:]) # 最好拷贝进去处理,不然万一在外面改了这个数组,堆就可能挂掉
print('初始化之后的数据:', heap.data)
# 取出堆顶的元素
print('取出的元素:', heap.get_one())
print(heap.data)
# 插入元素
heap.insert(31)
print('插入元素{}之后:'.format(31), heap.data)
return
if __name__ == '__main__':
# print(1//2)
main()
网友评论