导入
崩溃
学习如何调试一个崩溃的程序。
1import sys # 导入 sys 模块以获取系统相关的参数和函数 2import logging # 导入 logging 模块以生成日志消息 3 4logging.basicConfig(level=logging.INFO, format='%(asctime)s - %(levelname)s - %(message)s') # 配置 logging 模块，设置日志级别和格式 5 6class MinHeap: 7 def __init__(self): 8 # 初始化 MinHeap 类，使用空列表来存储堆中的值 9 self.heap = [] 10 11 # 将一个值插入堆中，并保持最小堆的性质 12 def insert(self, value): 13 logging.info("插入值 {} 到堆中".format(value)) # 记录日志，表示正在插入的值 14 self.heap.append(value) # 将值添加到堆列表末尾 15 self._bubble_up(len(self.heap) - 1) # 调用私有方法 _bubble_up 来恢复最小堆的性质 16 17 # 返回堆中的最小值（位于索引 0 的值） 18 def get_min(self): 19 logging.info("从堆中获取最小值") # 记录日志，表示正在获取最小值 20 return self.heap[0] # 返回索引 0 处的值，即堆中的最小值 21 22 # 移除并返回堆中的最小值，同时保持最小堆的性质 23 def remove_min(self): 24 logging.info("从堆中移除最小值") # 记录日志，表示正在移除最小值 25 min_value = self.heap[0] # 将最小值（索引 0 处的值）保存到变量中 26 last = self.heap.pop() # 移除堆的最后一个元素，并将其保存到变量 last 中 27 if len(self.heap) > 0: # 检查堆是否非空 28 self.heap[0] = last # 将最后一个元素移动到根位置 29 self._bubble_down(0) # 调用私有方法 _bubble_down 来恢复最小堆的性质 30 return min_value # 返回被移除的最小值 31 32 # 通过将指定索引处的值向上调整堆结构来恢复最小堆的性质 33 # 如果父节点的值大于当前值，则与父节点交换 34 def _bubble_up(self, index): 35 logging.info("将索引 {} 处的值向上冒泡".format(index)) # 记录日志，表示正在向上冒泡的值 36 parent = (index - 1) // 2 # 计算父节点的索引 37 while index > 0 and self.heap[parent] > self.heap[index]: # 当索引不在根节点且父节点值大于当前值时循环 38 self.heap[parent], self.heap[index] = self.heap[index], self.heap[parent] # 交换父节点和当前节点的值 39 index = parent # 将索引移动到父节点位置 40 parent = (index - 1) // 2 # 重新计算父节点的索引 41 42 # 通过将指定索引处的值向下调整堆结构来恢复最小堆的性质 43 # 如果当前值大于其子节点中的较小者，则与较小的子节点交换 44 def _bubble_down(self, index): 45 logging.info("将索引 {} 处的值向下冒泡".format(index)) # 记录日志，表示正在向下冒泡的值 46 smallest = index # 假设当前值是最小的 47 left_child = 2 * index + 1 # 计算左子节点的索引 48 right_child = 2 * index + 2 # 计算右子节点的索引 49 50 if left_child < len(self.heap) and self.heap[left_child] < self.heap[smallest]: # 检查左子节点是否存在且其值小于当前最小值 51 smallest = left_child # 将最小值的索引更新为左子节点的索引 52 53 if right_child < len(self.heap) and self.heap[right_child] < self.heap[smallest]: # 检查右子节点是否存在且其值小于当前最小值 54 smallest = right_child # 将最小值的索引更新为右子节点的索引 55 56 if smallest != index: # 检查当前值是否不是最小值 57 self.heap[index], self.heap[smallest] = self.heap[smallest], self.heap[index] # 交换当前值与最小子节点的值 58 self._bubble_down(smallest) # 递归调用 _bubble_down，传入新的索引 59 60 # 返回堆中指定索引处值的左右子节点 61 def get_children(self, index): 62 logging.info("获取索引 {} 处值的子节点".format(index)) # 记录日志，表示正在获取指定值的子节点 63 left_child = 2 * index + 1 # 计算左子节点的索引 64 right_child = 2 * index + 2 # 计算右子节点的索引 65 return self.heap[left_child], self.heap[right_child] # 返回左子节点和右子节点的值 66 67def main(): 68 min_heap = MinHeap() # 创建 MinHeap 类的实例 69 min_heap.insert(10) # 将值 10 插入堆中 70 min_heap.insert(5) # 将值 5 插入堆中 71 min_heap.insert(7) # 将值 7 插入堆中 72 min_heap.insert(20) # 将值 20 插入堆中 73 74 children = min_heap.get_children(3) # 最后一个元素没有子节点，因此会返回 (None, None) 75 76if __name__ == "__main__": 77 main()
1 - INFO - 获取索引 3 处值的子节点 2Traceback (most recent call last): 3 File "main.py", line 78, in <module> 4 main() 5 File "main.py", line 74, in main 6 children = min_heap.get_children(3) # 最后一个元素没有子节点 7 File "main.py", line 65, in get_children 8 return self.heap[left_child], self.heap[right_child] 9IndexError: 列表索引超出范围
1 File "main.py", line 65, in get_children 2 return self.heap[left_child], self.heap[right_child] 3IndexError: 列表索引超出范围
...
代码路径
12023-05-03 03:21:31,754 - INFO - 插入值 10 到堆中 22023-05-03 03:21:31,754 - INFO - 将索引 0 处的值向上冒泡 32023-05-03 03:21:31,754 - INFO - 插入值 5 到堆中 42023-05-03 03:21:31,754 - INFO - 将索引 1 处的值向上冒泡 52023-05-03 03:21:31,754 - INFO - 插入值 7 到堆中 62023-05-03 03:21:31,754 - INFO - 将索引 2 处的值向上冒泡 72023-05-03 03:21:31,754 - INFO - 插入值 20 到堆中 82023-05-03 03:21:31,754 - INFO - 将索引 3 处的值向上冒泡 92023-05-03 03:21:31,754 - INFO - 获取索引 3 处值的子节点
...
最小堆