手写堆（大顶堆/小顶堆）的实现

题目描述
手写堆（Heap）要求实现一个完整的大顶堆或小顶堆数据结构，支持插入元素、删除堆顶、获取堆顶值等核心功能，并保证堆的性质。堆是一种完全二叉树，通常用数组存储，大顶堆中每个节点的值都大于等于其子节点，小顶堆则相反。

核心思路
堆通过数组模拟完全二叉树，利用父子节点下标关系（父节点i，左子节点2i+1，右子节点2i+2）维护堆性质。关键步骤包括：

1. 上浮（Sift Up）：插入元素时，将其从底部向上调整至合适位置。
2. 下沉（Sift Down）：删除堆顶时，将末尾元素移至堆顶并向下调整。

实现步骤

1. 定义堆结构

   • 使用数组heap存储元素，size记录当前元素数量。
   • 通过构造函数指定大顶堆或小顶堆（可通过比较函数控制）。

2. 核心辅助方法

   • parent(i): 返回下标i的父节点下标(i-1)//2。
   • left(i), right(i): 返回左右子节点下标。
   • compare(a, b): 根据堆类型比较两元素（大顶堆返回a>b，小顶堆返回a<b）。

3. 上浮操作（Sift Up）

   • 从当前节点开始，与其父节点比较。
   • 若当前节点更优先（大顶堆中更大，小顶堆中更小），则与父节点交换。
   • 重复过程直至到达根节点或无需交换。

   def sift_up(self, i):
       while i > 0 and self.compare(self.heap[i], self.heap[self.parent(i)]):
           p = self.parent(i)
           self.heap[i], self.heap[p] = self.heap[p], self.heap[i]
           i = p
   

4. 下沉操作（Sift Down）

   • 从当前节点开始，与其左右子节点中更优先者比较。
   • 若子节点更优先，则交换并继续向下调整。
   • 重复直至到达叶子节点或无需交换。

   def sift_down(self, i):
       max_index = i
       l, r = self.left(i), self.right(i)
       # 找出当前节点、左子节点、右子节点中最优先者
       if l < self.size and self.compare(self.heap[l], self.heap[max_index]):
           max_index = l
       if r < self.size and self.compare(self.heap[r], self.heap[max_index]):
           max_index = r
       if i != max_index:
           self.heap[i], self.heap[max_index] = self.heap[max_index], self.heap[i]
           self.sift_down(max_index)  # 递归调整
   

5. 插入元素（Push）

   • 将新元素追加到数组末尾，增加size。
   • 对该元素执行上浮操作。

   def push(self, val):
       self.heap.append(val)
       self.size += 1
       self.sift_up(self.size - 1)
   

6. 删除堆顶（Pop）

   • 取出堆顶元素，将末尾元素移至堆顶，减少size。
   • 对堆顶执行下沉操作。

   def pop(self):
       if self.size == 0:
           raise Exception("Heap is empty")
       root = self.heap[0]
       self.heap[0] = self.heap[self.size - 1]
       self.heap.pop()
       self.size -= 1
       self.sift_down(0)
       return root
   

7. 获取堆顶（Peek）与判空

   • peek()返回heap[0]，is_empty()检查size是否为0。

复杂度分析

• 插入和删除操作的时间复杂度为O(log n)，因调整过程最多遍历树高。
• 建堆时间复杂度为O(n)（通过Floyd算法自底向上建堆）。

关键点

• 严格维护完全二叉树结构，确保数组连续存储。
• 上浮/下沉操作中，比较条件需根据堆类型灵活调整。
• 删除堆顶时，需先交换首尾元素再下沉，避免直接删除导致结构破坏。