python不调用heapq库 实现大顶堆，小顶堆

参考了博客，并对其进行了堆的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_note>=0 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_note>=0 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_note>=0 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]