Python 堆的时间复杂度是多少?

2023-04-11 00:00:00 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)。

相关文章