题目
最小堆的插入操作实现
信息
- 类型：问答
- 难度：⭐
考点
堆的性质维护,堆的插入操作,数组实现堆
快速回答
实现最小堆的插入操作需要：
- 将新元素添加到堆的末尾
- 执行上浮操作(swim)维护堆性质
- 时间复杂度为
O(log n)
关键步骤：
- 将元素插入数组末尾
- 与父节点比较，若更小则交换
- 重复步骤2直到满足堆性质
解析
原理说明
最小堆是一种完全二叉树，满足：任意节点的值都小于或等于其子节点的值。使用数组实现时：
- 父节点索引：
parent(i) = (i-1)//2 - 左子节点索引：
left_child(i) = 2*i + 1 - 右子节点索引：
right_child(i) = 2*i + 2
代码示例（Python）
class MinHeap:
def __init__(self):
self.heap = []
def insert(self, val):
# 1. 将新元素添加到末尾
self.heap.append(val)
# 2. 执行上浮操作
self._swim(len(self.heap) - 1)
def _swim(self, idx):
# 当不是根节点且小于父节点时上浮
while idx > 0:
parent_idx = (idx - 1) // 2
if self.heap[idx] >= self.heap[parent_idx]:
break
# 交换当前节点与父节点
self.heap[idx], self.heap[parent_idx] = self.heap[parent_idx], self.heap[idx]
idx = parent_idx最佳实践
- 使用
_swim私有方法封装上浮逻辑 - 在插入后立即维护堆性质
- 数组实现时注意索引从0开始
常见错误
- 忘记边界检查：上浮时未检查是否到达根节点
- 索引计算错误：父节点索引误用
i/2（应为(i-1)//2） - 比较方向错误：最小堆中误用
>比较（应使用<）
扩展知识
- 堆的删除操作：移除堆顶元素后，将末尾元素移到堆顶并执行下沉操作(sink)
- 优先队列应用：任务调度（最高优先级先执行）、Dijkstra算法（最短路径）
- 内置实现：Python的
heapq模块，Java的PriorityQueue
