Python 堆的时间复杂度是多少?
Python 堆的时间复杂度为 O(N log N),其中 N 表示堆中元素的个数。
堆的插入、删除最小元素的时间复杂度为 O(log N),因为这两个操作都要调整堆的结构。
以下是使用 Python 的 heapq 实现堆的代码演示:
import heapq # 初始化堆 heap = [] # 往堆中插入元素 heapq.heappush(heap, 5) heapq.heappush(heap, 2) heapq.heappush(heap, 7) # 取出堆中最小元素 min_element = heapq.heappop(heap) # 打印堆中剩余元素 print(heap)
输出结果为:
[5, 7]
以上代码中,heapq.heappush()
和 heapq.heappop()
操作均需要 O(log N) 的时间复杂度。因此,插入 N 个元素到堆中的时间复杂度为 O(N log N),删除 N 个元素的时间复杂度也为 O(N log N)。
相关文章