前言
做了太久的前端崽好久没刷题，居然忘了最大最小堆，这里梳理一下。
最大堆（Max Heap）
定义
每个父节点的值大于或等于其子节点的值。
性质
根节点是整个堆中的最大值。
插入或删除元素时，通过“上浮”（swim）或“下沉”（sink）操作维护堆性质。
操作
- 插入：将新元素添加到末尾，逐步与其父节点比较并交换，直到满足父节点 ≥ 子节点。
- 删除最大值：移除根节点（最大值），将最后一个元素移到根位置，逐步与其较大的子节点交换，直到恢复堆性质。
应用：优先队列（快速获取最大值）、堆排序算法。
最小堆（Min Heap）
定义
每个父节点的值小于或等于其子节点的值。
性质
根节点是整个堆中的最小值。
插入或删除元素时，同样通过“上浮”或“下沉”操作维护堆性质。
操作
- 插入：将新元素添加到末尾，逐步与其父节点比较并交换，直到满足父节点 ≤ 子节点。
- 删除最小值：移除根节点（最小值），将最后一个元素移到根位置，逐步与其较小的子节点交换，直到恢复堆性质。
应用：优先队列（快速获取最小值）、Dijkstra算法、合并K个有序链表。
共同特点
完全二叉树结构：可以用数组紧凑表示，无需指针。
父节点索引为 i，则左子节点为 2i+1，右子节点为 2i+2。
子节点索引为 i，则父节点为 ⌊(i-1)/2⌋。
时间复杂度：
插入（O(log n)）、删除极值（O(log n)）、获取极值（O(1)）。
空间复杂度：O(n)。
典型应用场景
最大堆：快速获取数据流中的前K大元素。
最小堆：快速获取数据流中的前K小元素。
堆排序：利用最大堆升序排序，或最小堆降序排序。
睿哥知道我忘了这个能打死我= =。。。