堆（Heap）

堆是一种特殊的树：

  • 堆中的每一个节点值都大于等于（或小于等于）子树中所有节点的值。或者说，任意一个节点的值都大于等于（或小于等于）所有子节点的值。

复杂度分析：

  1. 初始化：O(n)
  2. 插入、查找或删除：O(logn)
  3. 和有序数组的区别：查找是O(1)，但涉及插入或删除则是O(n); 初始化是O(logn)

最大堆/最小堆：

  • 父节点>子节点 - 最大堆；
  • 父节点<子节点 - 最小堆；

存储形式：

  • 完全二叉树

两种操作：

插入元素（最大堆为例）：

  1. 将待插入的元素放在最后
  2. 从底向上，如果大于父节点，则交换父子节点

删除堆顶元素（最大堆为例）（又叫堆化）：

  1. 自底向上：遍历每个节点，比较左右子节点取最大上升为父节点（缺点-中间节点出现气泡，浪费存储空间）
  2. 自顶向下：选择末尾元素置于堆顶，比较左右子节点取最大上升为父节点，直到无法交换。

最大堆排序：

  1. 建堆：对所有非叶节点进行堆化，顺序从后往前
  2. 排序：删除堆顶元素+自顶向下堆化 = 交换堆顶元素和数组最后元素。（由于堆大小减少，排序中被置于末尾的堆顶元素不会被再次被排序）