高级数据结构

优先队列的本质是一个二叉堆结构。堆在英文里叫 Binary Heap，它是利用一个数组结构来实现的完全二叉树。换句话说，优先队列的本质是一个数组，数组里的每个元素既有可能是其他元素的父节点，也有可能是其他元素的子节点，而且，每个父节点只能有两个子节点，很像一棵二叉树的结构。

牢记下面优先队列有三个重要的性质。

1. 数组里的第一个元素 array[0] 拥有最高的优先级别。
2. 给定一个下标 i，那么对于元素 array[i] 而言：
   • 它的父节点所对应的元素下标是 (i-1)/2
   • 它的左孩子所对应的元素下标是 2×i + 1
   • 它的右孩子所对应的元素下标是 2×i + 2
3. 数组里每个元素的优先级别都要高于它两个孩子的优先级别。

优先队列最基本的操作有两个。

1. 向上筛选（sift up / bubble up）
   时间复杂度：O(logk)
2. 向下筛选（sift down / bubble down）
   时间复杂度：O(logk)

初始化一个大小为 n 的堆，所需要的时间是 O(n)

排序

基本&常考

• 冒泡排序（Bubble Sort） O(n²) o
• 插入排序（Insertion Sort） O(n²) o
• 归并排序（Merge Sort） O(nlogn)/O(n) o
• 快速排序（Quick Sort） O(nlogn)-O(n²)/O(logn) o
• 拓扑排序（Topological Sort）
  其他排序算法
• 堆排序（Heap Sort）
• 桶排序（Bucket Sort)

递归与回溯

递归

• 汉诺塔
  时间复杂度：
• 迭代法 !
• 公式法 !