LeetCode 堆的初始化题解

LeetCode 堆的初始化题解题目描述介绍堆的初始化方法。堆的初始化什么是堆堆是一种完全二叉树分为最大堆和最小堆。最大堆中每个节点的值都大于等于其子节点的值最小堆中每个节点的值都小于等于其子节点的值。初始化方法插入法逐个插入元素时间复杂度 O(n log n)批量法将所有元素放入数组然后从最后一个非叶子节点开始向下调整时间复杂度 O(n)代码实现import heapq # 插入法 def heap_insert(arr): heap [] for num in arr: heapq.heappush(heap, num) return heap # 批量法 def heap_build(arr): heap arr[:] n len(heap) for i in range(n // 2 - 1, -1, -1): heapq._siftup(heap, i) return heap # 测试 def test_heap(): arr [1, 2, 3, 4, 5] print(heap_insert(arr)) # 输出[1, 2, 3, 4, 5] print(heap_build(arr)) # 输出[1, 2, 3, 4, 5] if __name__ __main__: test_heap()总结堆的初始化有两种方法批量法的时间复杂度更优。