堆就是用数组实现的二叉树，所以不使用父指针和子指针。堆分为两种：最大堆和最小堆。
最大堆：父结点的值比每一个子节点的值都要大
最小堆：父结点的值比每一个子节点的值都要小
''' 堆的常用用法： 1.构建优先队列 2.支持堆排序 3.快速找出最大值或最小值 ''' import math class Heap: def __init__(self, A): self.A = A # 维护最大堆的属性 def MaxHeapify(self, i): # 考虑到python列表元素索引以0开始, 每个元素的左子元素的索引为2i+1,右子元素的索引为2i+2 left_child = 2 * i + 1 right_child = left_child + 1 if left_child < len(self.A) and self.A[left_child] > self.A[i]: largest = left_child else: largest = i if right_child < len(self.A) and self.A[right_child] > self.A[largest]: largest = right_child if largest != i: temp = self.A[i] self.A[i] = self.A[largest] self.A[largest] = temp self.MaxHeapify(largest) # 创建最大堆 def BuildMaxHeap(self): for i in range(math.floor((len(self.A) / 2)), -1, -1): self.MaxHeapify(i) # 维护最小堆的属性 def MinHeapify(self, i): # 考虑到python列表元素索引以0开始, 每个元素的左子元素的索引为2i+1,右子元素的索引为2i+2 left_child = 2 * i + 1 right_child = left_child + 1 if left_child < len(self.A) and self.A[left_child] < self.A[i]: least = left_child else: least = i if right_child < len(self.A) and self.A[right_child] < self.A[least]: least = right_child if least != i: temp = self.A[i] self.A[i] = self.A[least] self.A[least] = temp self.MinHeapify(least) # 创建最小堆 def BuildMinHeap(self): for i in range(math.floor((len(self.A) / 2)), -1, -1): self.MinHeapify(i) # 最大堆移除最大值 def remove_max(self): self.BuildMaxHeap() pop_value = self.A.pop(0) self.BuildMaxHeap() return pop_value # 插入值 def heap_insert(self, insert_value): self.A.append(insert_value) self.BuildMaxHeap() # 替换指定索引的值 def heap_replace(self, replace_index, replace_value): self.A[replace_index] = replace_value self.BuildMaxHeap() # 删除指定索引元素 def remove_at_index(self, remove_index): self.A.pop(remove_index) self.BuildMaxHeap() # 堆排序算法 def heap_sort(self): self.BuildMaxHeap() sorted_array = [] for i in range(len(self.A)-1, -1, -1): sorted_array.append(self.remove_max()) return sorted_array if __name__ == '__main__': # A2 = [6, 4, 9, 4, 3, 7, 1, 6] # heap_min = Heap(A2) # 创建最小堆 # heap_min.BuildMinHeap() # print(heap_min.A) A = [6, 4, 9, 3, 7, 1, 5, 6, 8] heap_max = Heap(A) # 创建最大堆 heap_max.BuildMaxHeap() print(heap_max.A) # 移除最大堆最大值 # res = heap_max.remove_max() # print(res) # print(heap_max.A) # 堆排序 # sort_res = heap_max.heap_sort() # print(sort_res) # 插入 # heap_max.heap_insert(12) # print(heap_max.A) # 替换(已经堆排序再替换) # heap_max.heap_replace(3, 15) # print(heap_max.A) # 删除 heap_max.remove_at_index(1) print(heap_max.A)