算法导论读书笔记（6）堆排序

时间：2021-05-03 17:07:54

第二部分 排序和顺序统计量

第6章 堆排序

  1. 复杂度O(nlgn)
  2. 原址排序
  3. 集插入排序和归并排序两者的优点

1. 堆

  • 堆是一个数组，可看成一个近似的完全二叉树
  • 除了最底层外，该树是完全充满的
  • 从左向右填充
  • 堆的高度 = 根结点的高度

  • 堆结构上一些基本操作的运行时间至多与树的高度成正比，即时间复杂度为O(lgn)

    表示堆的数组A包括两个属性

    1. A.length给出数组中元素的个数
    2. A.heap-size表示有多少个堆元素存储在该数组中

算法导论读书笔记（6）堆排序
计算给定节点下标i的父，左孩子，右孩子的下标

Parent(i) return i/2
Left(i) return 2i
Right(i) return 2i + 1

最大堆（堆中最大元素存放在根结点）

  • A[Parent(i)] >= A[i]

最小堆（堆中最小元素存放在根结点）

  • A[Parent(i)] <= A[i]
  • 通过用过构造优先队列

2. 维护堆的性质

算法导论读书笔记（6）堆排序
从A[i]、A[Left(i)]和A[Right(i)]中选出最大的，并将下标存储在largest中。如果A[i]是最大的，程序结束。否则，最大元素是i的某个孩子结点，则交换A[i]和A[largest]的值，从而使i及其孩子都满足最大堆的性质。在交换后，下标为largest的结点的值是原来的A[i]，于是以该结点为根的子树又可能会违反最大堆的性质，因此，需要对孩子树递归调用Max-heapify

Max-Heapify(A, i)
    l = Left(i)
    r = Right(i)

    if l <= A.heap-size and A[l] > A[i]
        largest = l
    else
        largest = i
    if r <= A.heap-size and A[r] > A[largest]
        largest = r

    if largest != i
        exchange A[i] with A[largest]
        Max-Heapify(A, largest)

Max-heapify的时间复杂度为O(h)， h = 树高。
当用数组存储n个元素的堆时，叶结点下标分别是⌊n/2⌋+1, ⌊n/2⌋+2, …, n.

3. 建堆

算法导论读书笔记（6）堆排序
用自底向上的方法利用过程Max-heapify把一个大小为n = A.length的数组A[1..n]转换为最大堆。

Build-Max-Heap(A)
    A.heap-size = A.length
    for i = ⌊A.length/2⌋ downto 1
        Max-Heapify(A, i)

每次调用Max-Heapify的时间复杂度是O(lgn)，Build-Max-Heap需要O(n)次这样的调用。因此总的时间复杂度是O(nlgn)。这个上界虽然正确，但不是渐近紧确。

4. 堆排序

算法导论读书笔记（6）堆排序
先建成最大堆，因数组中最大的元素在根结点A[1]，通过把它与A[n]互换，可以保存最大的元素并从堆中去掉结点n，剩余的结点中，原来根的孩子结点仍然是最大堆，而新的根结点可能会违背最大堆的性质，因此需要调用Max-Heapify(A, 1)构造一个新的最大堆，不断重复这一过程，直到堆的大小降到2。

Heapsort(A)
    Build-Max-Heap(A)
    for i = A.length downto 2
    exchange A[1] with A[i]
    A.heap-size = A.heap-size - 1
    Max-Heapify(A, 1)

时间复杂度O(nlgn)

5. 优先队列（用堆实现）

优先队列有两种形式
1. 最大优先队列
2. 最小优先队列，可被用于基于事件驱动的模拟器。队列中保存要模拟的事件，每个事件都有一个发生时间作为其关键字。事件必须按照发生的时间顺序进行模拟，因为某一事件的模拟结果可能会触发对其他事件的模拟

Heap-Maximum(A)
    return A[1]
Heap-Extract-Max(A)
    if A.heap-size < 1
        error "heap underflow"
    max = A[1]
    A[1] = A[A.heap-size]
    Max-Heapify(A, 1)
    return max

算法导论读书笔记（6）堆排序

修改关键字的大小后，当前元素会不断地与其父结点进行比较，如果当前元素的关键字较大，则当前元素与其父结点进行交换。不断重复该过程，直到当前元素的关键字小于其父结点时终止。

Heap-Increase-Key(A, i, key)
    if key < A[i]
        error "new key is smaller than currenty key"
    A[i] = key
    while i > 1 and A[Parent(i)] < A[i]
        exchange A[i] with A[Parent(i)]
        i = Parent(i)
首先增加一个叶结点来扩展最大堆，然后调用Heap-Increase-Key为新结点设置对应的关键字，同时保存最大堆的性质

Max-Heap-Insert(A, key) A.heap-size = A.heap-size + 1 A[A.heap-size] = 0 Heap-Increase-Key(A, A.heap-size, key)
标签：

相关文章