网站建站网站80s隐秘而伟大,wordpress文章如何备份,湖南长大建设集团股份有限公司网站,二手交易平台参考了博客#xff0c;并对其进行了堆的push() 和 降序排序的补充
【精选】图解堆排序及其Python实现_python 实现小顶堆-CSDN博客
目录
大顶堆
调用结果展示#xff1a;
小顶堆#xff1a;
调用结果展示#xff1a;
此结果与调用heapq库中的heapify(arr)函数等效
…参考了博客并对其进行了堆的push() 和 降序排序的补充
【精选】图解堆排序及其Python实现_python 实现小顶堆-CSDN博客
目录
大顶堆
调用结果展示
小顶堆
调用结果展示
此结果与调用heapq库中的heapify(arr)函数等效
其中定义的push()函数与heapy库中的heappush(arr,num)函数等效
大顶堆
import copy
# 导入copy 后面用到深拷贝 为排序不改变原值考虑class Heap(object):实现大顶堆及堆排序def __init__(self, arr: list):arr: 用户输入的待排序数组self.arr arrself.len len(arr)# self.sorted1_arr []self.sorted2_arr []# 一旦创建类即自动转为大顶堆数组self.create_heap()def heapify(self, parent_index):维护堆的性质# 假设当前父节点是子树中最大的值下标largest parent_index# 左右孩子节点下标有可能不存在left_child_index parent_index * 2 1right_child_index parent_index * 2 2# 判断左右子节点是否存在并找出其中最大的值下标if left_child_index self.len and self.arr[largest] self.arr[left_child_index]:largest left_child_indexif right_child_index self.len and self.arr[largest] self.arr[right_child_index]:largest right_child_index# 需要进行位置调整并进行递归调整if not (largest parent_index):self.arr[parent_index], self.arr[largest] self.arr[largest], self.arr[parent_index]self.heapify(largest)def create_heap(self):初始化堆last_parent_index (self.len - 1) // 2 # 最后一个包含子节点的父节点下标for i in range(last_parent_index, -1 , -1):self.heapify(i)def pop(self):peak self.arr[0]# 交换堆顶与最后一个元素然后重新建堆self.arr[0] self.arr[-1]self.arr.pop(-1)self.len - 1self.heapify(0) # 从上到下维护堆return peak# 在某人博客基础上加了增加元素的def push(self,elem):self.arr.append(elem)self.len 1 # 记录加入元素的下标及父节点下标tmp self.len - 1parent_note (tmp-1) // 2# 在所加入的那一条链上 不断比较与父节点的大小 并交换while parent_note0 and self.arr[parent_note] self.arr[tmp]:self.arr[parent_note], self.arr[tmp] self.arr[tmp], self.arr[parent_note]# 更新加入节点和父节点的下标tmp parent_noteparent_note (parent_note-1) // 2def heap_sort1(self):堆排序输出排序后的数组升序self.arr2 copy.deepcopy(self.arr)self.sorted1_arr [0] * len(self.arr)for i in range(len(self.arr)-1,-1,-1):self.sorted1_arr[i] self.pop()self.arr self.arr2return self.sorted1_arrdef heap_sort2(self):堆排序输出排序后的数组降序self.arr2 copy.deepcopy(self.arr)for i in range(len(self.arr)):self.sorted2_arr.append(self.pop())self.arr self.arr2return self.sorted2_arr
调用结果展示
h Heap([18, 34, 26, 25, 30, 8, 28, 13])
print(h.arr)
print(h.pop())
h.push(36)
print(h.arr)
print(h.heap_sort2())
print(h.heap_sort1())#结果展示
[34, 30, 28, 25, 18, 8, 26, 13]
34
[36, 25, 30, 13, 18, 8, 26, 28]
[36, 30, 28, 26, 25, 18, 13, 8]
[25, 30, 13, 18, 8, 26, 28, 36]
小顶堆
搞懂大顶堆 小顶堆很快秒 只需改几个符号
import copy
# 导入copy 后面用到深拷贝 为排序不改变原值考虑class Heap(object):实现小顶堆及堆排序def __init__(self, arr: list):arr: 用户输入的待排序数组self.arr arrself.len len(arr)# self.sorted1_arr []self.sorted2_arr []# 一旦创建类即自动转为大顶堆数组self.create_heap()def heapify(self, parent_index):维护堆的性质# 假设当前父节点是子树中最小的值下标largest parent_index# 左右孩子节点下标有可能不存在left_child_index parent_index * 2 1right_child_index parent_index * 2 2# 判断左右子节点是否存在并找出其中最小的值下标if left_child_index self.len and self.arr[largest] self.arr[left_child_index]:largest left_child_indexif right_child_index self.len and self.arr[largest] self.arr[right_child_index]:largest right_child_index# 需要进行位置调整并进行递归调整if not (largest parent_index):self.arr[parent_index], self.arr[largest] self.arr[largest], self.arr[parent_index]self.heapify(largest)def create_heap(self):初始化堆last_parent_index (self.len - 1) // 2 # 最后一个包含子节点的父节点下标for i in range(last_parent_index, -1 , -1):self.heapify(i)def pop(self):peak self.arr[0]# 交换堆顶与最后一个元素然后重新建堆self.arr[0] self.arr[-1]self.arr.pop(-1)self.len - 1self.heapify(0) # 从上到下维护堆return peak# 在某人博客基础上加了增加元素的def push(self,elem):self.arr.append(elem)self.len 1 # 记录加入元素的下标及父节点下标tmp self.len - 1parent_note (tmp-1) // 2# 在所加入的那一条链上 不断比较与父节点的大小 并交换while parent_note0 and self.arr[parent_note] self.arr[tmp]:self.arr[parent_note], self.arr[tmp] self.arr[tmp], self.arr[parent_note]# 更新加入节点和父节点的下标tmp parent_noteparent_note (parent_note-1) // 2def heap_sort1(self):堆排序输出排序后的数组降序self.arr2 copy.deepcopy(self.arr)self.sorted1_arr [0] * len(self.arr)for i in range(len(self.arr)-1,-1,-1):self.sorted1_arr[i] self.pop()self.arr self.arr2return self.sorted1_arrdef heap_sort2(self):堆排序输出排序后的数组升序self.arr2 copy.deepcopy(self.arr)for i in range(len(self.arr)):self.sorted2_arr.append(self.pop())self.arr self.arr2return self.sorted2_arr
调用结果展示
h Heap([18, 34, 26, 25, 30, 8, 28, 13])
print(h.arr)
print(h.pop())
h.push(36)
print(h.arr)
print(h.heap_sort2())
print(h.heap_sort1())#结果展示
[8, 13, 18, 25, 30, 26, 28, 34]
8
[13, 25, 18, 34, 30, 26, 28, 36]
[13, 18, 25, 26, 28, 30, 34, 36]
[25, 18, 34, 30, 26, 28, 36, 13] 基于python中的此库只能实现小顶堆
此结果与调用heapq库中的heapify(arr)函数等效
import heapqarr [18, 34, 26, 25, 30, 8, 28, 13]
heapq.heapify(arr)
print(arr)#结果
[8, 13, 18, 25, 30, 26, 28, 34]
其中定义的push()函数与heapy库中的heappush(arr,num)函数等效
将上述push()函数单独拿出来 就可以模拟heappush()功能
def push(arr,elem):arr.append(elem)n len(arr)# 记录加入元素的下标及父节点下标tmp n - 1parent_note (tmp-1) // 2# 在所加入的那一条链上 不断比较与父节点的大小 并交换while parent_note0 and arr[parent_note] arr[tmp]:arr[parent_note], arr[tmp] arr[tmp], arr[parent_note]# 更新加入节点和父节点的下标tmp parent_noteparent_note (parent_note-1) // 2arr [10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21]
arr1 []
for item in arr:push(arr1,item)
print(arr1)#结果
[5, 7, 21, 15, 10, 24, 27, 45, 17, 30, 36, 50]
heappush(arr,num)的效果可见效果一致
import heapqarray [10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21]
heapq.heapify(array)#结果
[5, 7, 21, 15, 10, 24, 27, 45, 17, 30, 36, 50]
