堆(Heap)

定义

堆是一种满足堆序性质的完全二叉树：在大顶堆中，每个父节点的值都不小于其子节点；小顶堆则相反。堆通常用数组紧凑存储，无需指针。

原理

对于数组下标 i 的节点，其左子节点为 2i+1、右子节点为 2i+2、父节点为 (i-1)/2。插入时把元素放到末尾再向上上浮调整；删除堆顶时用末尾元素填补堆顶再向下下沉调整。这两种调整都沿树高进行。建堆可以自底向上在 O(n) 时间完成。

复杂度

• 取堆顶（最值）：O(1)
• 插入：O(log n)
• 删除堆顶：O(log n)
• 建堆：O(n)

应用场景

• 优先队列
• 堆排序
• 求 Top K 问题
• Dijkstra、Prim 等图算法