红黑树

红黑树起源
image.png
红黑树定义
image.png
红黑树属性
image.png
image.png
右倾斜旋转为左倾斜：保持对称的顺序、黑平衡
image.png
image.png
颜色翻转：
image.png
image.png
image.png
image.png
image.png
image.png

堆排序

时间复杂度O（nlogn），空间复杂度O（1）

  1. 将无序A数列构建一个堆，如最大堆。（Ο(n)）
  2. 将堆进行max_heapify修正为最大堆。（Ο(log2n)）
  3. 找到最大值元素A[1]，即当前最大堆的跟节点。（Ο(1)）
  4. 将A[1]和堆最后的元素A[n]进行交换。（Ο(1)）
  5. 将元素A[n]撤出堆，减少堆大小。（Ο(1)）
  6. 现在堆也许会违背最大堆属性，因此重复2-5步骤。（有n steps）

具体：

  1. 堆近似完全二叉树

分为小根堆（父节点≤左右儿子）和大根堆（父节点≥左右儿子）
可以用一维数组存储堆
算法与数据结构 - 图13

  1. 建堆

以自底向上的方式，从i = n/2结点位置依次向上遍历进行堆调整操作
算法与数据结构 - 图14

  1. 堆排序时间复杂度
  • 建堆O（n）
  • 由于交换根节点和最后的节点，再移除最后的节点，堆的大小不断减少，所有的堆调整操作时间复杂度：O(log1+log2+…+logn) = (log(n!)) ≈ O(nlogn)

最后堆排序的时间复杂度为Ο(n)
[MIT6.006] 4. Heaps and Heap Sort 堆，堆排序
时间复杂度：O(log1+log2+…+logn)=O(log(n!))=O(nlogn)