9.1 堆基础

In computer science, a heap is a specialized tree-based data structure that satisfies the heap property: In a max heap, for any given node C, if P is a parent node of C, then the key (the value) of P is greater than or equal to the key of C. In a min heap, the key of P is less than or equal to the key of C. The node at the "top" of the heap (with no parents) is called the root node.

堆是一种特殊的树形结构, 通常用完全二叉树实现; 堆分为两类:

• 最大堆: 节点大于等于其子节点
• 最小堆: 节点小于等于其子节点

因为完全二叉树可以用数组表示, 那么堆也可以.

对于长度为n的数组$N_0, ..., N_{i-1}, N_i, N_{i+1}, ..., N_{n-1}$ , 节点$N_i$ :

• 父节点为: $N_{\frac{i-1}{2}}$, 下标为 $\frac{i-1}{2}$
• 左右子节点分别为: $N_{2i+1}, N_{2i+2}$

堆的操作, 以最大堆为例:

• 插入:
  1. 从上至下, 从左至右, 找到第一个空缺位置插入新节点
  2. 新节点大于父节点, 则交换, 直到小于等于父节点为止
• 删除堆顶节点:
  1. 将最下层最右边的节点移动至堆顶
  2. 根节点大于子节点, 和较大的子节点交换, 直到小于等于子节点为止

插入和删除需要交换节点, 最多交换深度h次, 那么时间复杂度为O(logn)

Reference

1. 剑指Offer（专项突破版）
2. Heap wiki