我买的牛客网正版的《算法入门与基础提升》 这是2.6节的重要内容：堆排序的实现 本文实现的是大根堆 用动态数组实现 即 录入（调用heap_insert方法）时总保持动态数组的index=0位置为最大值 返回最大值（调用pop_max方法）时，将[0]返回，并将[0]与[有效长度-1]互换， 然后将更换位置后的新[0]和自己的孩子们比，小的下沉，大的变为[0] 此后循环，直至孩子们不比自己大，或已沉底
class Heap:#大根堆 def __init__(self,N): self.heap = [] self.used_length = 0 self.max_length = N def heap_insert(self,val): self.heap.append(val) self.used_length += 1 index = self.used_length - 1 while (self.heap[index] > self.heap[(index-1)//2]) and (index > 0): self.heap[index],self.heap[(index-1)//2] = self.heap[(index-1)//2], self.heap[index] index = (index-1)//2 def _heapify(self,index=0): left = index*2 + 1 while left < self.used_length: #此时下方还有孩子 largest = left + 1 if (left+1<self.used_length) and (self.heap[left+1]>self.heap[left]) else left #当右孩子不越界且右孩子大于左孩子，largest给右孩子，否则给左孩子 largest = largest if self.heap[largest] > self.heap[index] else index if largest == index:#此时index位置上的数仍是自己、左右孩子中最大的 break else: self.heap[index],self.heap[largest] = self.heap[largest],self.heap[index] index = largest left = index * 2 + 1 def pop_max(self): res = self.heap[0] self.heap[0],self.heap[self.used_length-1] = self.heap[self.used_length-1],self.heap[0] self.heap.pop(self.used_length-1) self.used_length -= 1 self._heapify(0) return res def show_all(self): return self.heap[:self.used_length]