算法导论读书笔记(3)

I.堆以及堆排序

（二叉） 堆 数据结构是一种数据结构，它可以被视为一棵完全二叉树。树中每个结点与数组中存放该结点值的那个元素对应。树的每一层都是填满的，最后一层从左子树开始填。表示堆的数组 A 是一个具有两个属性的对象： A.length 是数组中元素的个数， A.heap-size 是存放在 A 中的堆元素个数。此处有 A.heap-size <= A.length 。树的根为 A [ 1 ]，给定了某个结点的下标 i ，其父结点 PARENT(i) ，左儿子 LEFT(i) 和右儿子 RIGHT(i) 的下标可以简单的计算出来。

PARENT(i) 1 return FLOOR(i/2);

LEFT(i) 1 return 2*i;

RIGHT(i) 1 return 2*i + 1

我们这里所说的堆有两种，分别是最大堆和最小堆。 大根堆:最大堆特性是指除了根以外的每个结点 i，有 A [ PARENT(i) ] >= A [ i ]。即某个结点的值至多和其父结点一样大。这样，堆中的最大元素就存放在根结点中. 小根堆:最小堆特性是指除了根以外的每个结点 i ，有 A [ PARENT(i) ] <= A [ i ]，最小堆的最小元素是在根.

堆可以被看成是一棵树，结点在堆中的高度定义为从本结点到叶子的最长简单下降路径上边的数目；定义堆的高度为树根的高度，因而树的高度为 Θ (lg n )。而堆结构上的一些基本操作的运行时间至多与树的高度成正比，为 O (lg n )。下面将介绍几个基本过程，并说明它们的用法。

• Max_Heapify 过程 运行时间是O(lgn)，是保持最大堆性质的关键

• BUILD-MAX-HEAP 过程，以线性时间运行，可以在无序的输入数组上构造出最大堆

• HEAP-SORT 过程，运行时间为 O ( n lg n )，对一个数组进行原地排序

1.保持堆的性质  Max_Heapify ：当 MAX-HEAPIFY 被调用时，我们假定以 LEFT(i) 和 RIGHT(i) 为根的两棵二叉树都是最大堆，但这时 A [ i ]可能小于其子女，这样就违反了最大堆特性。 MAX-HEAPIFY 让 A [ i ]在最大堆中“下降”，使以_i_ 为根的子树成为最大堆

伪代码

MAX-HEAPIFY(A, i) 1 l = LEFT(i) 2 r = RIGHT(i) 3 if l <= A.heap-size and A[l] > A[i] 4 largest = l 5 else 6 largest = i 7 if r <= A.heap-size and A[r] > A[largest] 8 largest = r 9 if largest != i 10 exchange A[i] with A[largest] 11 MAX-HEAPIFY(A, largest)

因为是从向下进行下降，所以经过的路程最坏情况就是树高 logn 所以此步骤的运行时间是O(logn)

2.下图描述了 MAX-HEAPIFY 的过程。在算法的每一步里，从元素 A [ i ]， A [ LEFT(i) ]和 A [ RIGHT(i) ]中找出最大的，并将其下标保存在 largest 中。如果 A [ i ]是最大的，则以 i 为根的子树已是最大堆，程序结束。否则，交换 A [ i ]和 A [ largest]，从而使 i 及其子女满足堆性质。下标为 largest 的结点在交换后的值为 A [ i ]，以该结点为根的子树可能又违反了最大堆性质。因而要对该子树递归调用 MAX-HEAPIFY 。

2.建堆 Build_Max_Heap(A)

现在可以自底向上地用 MAX-HEAPIFY 来将一个数组 A [ 1 .. n ]（此处 n = A.length ）变成一个最大堆。又可知子数组 A [FLOOR(n / 2) + 1 .. n ]中的元素都是树中的叶子结点，它们都可以看做是只含一个元素的堆。过程 BUILD-MAX-HEAP 对树中的每一个非叶子结点都调用了一次 MAX-HEAPIFY

BUILD-MAX-HEAP(A) 1 A.heap-size = A.length 2 for i = FLOOR(A.length / 2) downto 1 3 MAX-HEAPIFY(A, i)

如图所示:

调用了n次的Max_Heapify()  所以运行时间是O(nlgn)

但是这个不怎么正确，因为在每一次下降的过程中，树的高度也在不断的下降，所以不会一直有lgn那么大，nlgn只是一个上界，但不是一个更加紧确的界。

MAX-HEAPIFY 作用在高度为 h 的结点上的时间为 O ( h )，可以将 BUILD-MAX-HEAP 的代价表示为：

最终可以得出 BUILD-MAX-HEAP 过程运行时间的界为

3.堆排序算法

堆排序算法先用 BUILD-MAX-HEAP 将输入数组 A [ 1 .. n ]建成一个最大堆。此时数组中最大元素在根 A [ 1 ]，可以通过将它与_A_ [ n ]互换来达到最终正确的位置。然后通过缩小 A.heap-seize ，可以很容易地将 A [ 1 .. n - 1 ]建成最大堆。不断的重复这一过程，堆的大小由 n - 1一直降到2。

伪代码

HEAP-SORT(A) 1 BUILD-MAX-HEAP(A) 2 for i = A.length downto 2 3 exchange A[1] with A[i] 4 A.heap-size = A.heap-size - 1 5 MAX-HEAPIFY(A, 1)

堆排序算法的C++实现

#include <iostream>
using namespace std;

void MAX_HEAPIFY(int a[], int i, int n)
{
    int l, r, largest;
    l = 2 * i;
    r = (2 * i + 1);
    if ((l <= n) && a[l] > a[i])
        largest = l;
    else
        largest = i;
    if ((r <= n) && (a[r] > a[largest]))
        largest = r;
    if (largest != i)
    {
        swap(a[i], a[largest]);
//      loc = a[i];
//      a[i] = a[largest];
//      a[largest] = loc;
        MAX_HEAPIFY(a, largest, n);
    }
}
void BUILD_MAX_HEAP(int a[], int n)
{
    for (int k = n / 2; k >= 1; k--)
    {
        MAX_HEAPIFY(a, k, n);
    }
}
void HEAPSORT(int a[], int n)
{

    BUILD_MAX_HEAP(a, n);
    int i, temp;
    for (i = n; i >= 2; i--)
    {
        temp = a[i];
        a[i] = a[1];
        a[1] = temp;
        MAX_HEAPIFY(a, 1, i - 1);
    }
}

void main()
{
    int a[11] = { 0, 9, 8, 7, 6, 5, 4, 3, 2, 1,0 };
    HEAPSORT(a, 10);
    cout << ":::::::SORTED FORM::::::" << endl;
    for (int i = 1; i <= 10; i++)
    {
        cout << a[i] << endl;
    }
    system("pause");
}

II 优先队列

堆的一个很常见的应用：作为高效的 优先级队列 （priority queue）。队列也有两种：最大优先级队列和最小优先级队列。

优先级队列 是一种用来维护由一组元素构成的集合 S 的数据结构，这一组元素中的每一个都有一个关键字 key 。一个 最大优先级队列 支持以下操作：

• INSERT(S, x) ：把元素 x 插入集合。
• MAXIMUM(S) ：返回 S 中具有最大关键字的元素。
• EXTRACT-MAX(S) ：去掉并返回 S 中具有最大关键字的元素。
• INCREASE-KEY(S, x, k) ：将元素 x 的关键字值增加到 k ，这里 k 值不能小于 x 的原关键字值。

最大优先级队列的一个应用是在一台分时计算机上进行作业调度。 最小优先级队列 支持的操作包括 INSERT ， MINIMUM ，EXTRACT-MIN ， DECREASE-KEY 。这种队列可被用在基于事件驱动的模拟器中。

下面是最大优先级队列的操作。过程 HEAP-MAXIMUM 用 Θ (1)的时间实现了 MAXIMUM 操作

HEAP-MAXIMUM(A) 1 return A[1]

过程 HEAP-EXTRACT-MAX 实现了 EXTRACT-MAX 操作。

HEAP-EXTRACT-MAX(A)
1 if A.heap-size < 1
2     error "heap underflow"
3 max = A[1]
4 A[1] = A[A.heap-size]
5 A.heap-size = A.heap-size - 1
6 MAX-HEAPIFY(A, 1)
7 reutrn max

HEAP-EXTRACT-MAX 的运行时间为 O (lg n )。

过程 HEAP-INCREASE-KEY 实现了 INCREASE-KEY 操作。

HEAP-INCREASE-KEY(A, i, key)
1 if key < A[i]
2     error "new key is smaller than current key"
3 A[i] = key
4 while i > 1 and A[PARENT(i)] < A[i]
5     exchange A[i] with A[PARENT(i)]
6     i = PARENT(i)

下图是 HEAP-INCREASE-KEY 操作的一个示例。在 n 元堆上， HEAP-INCREASE-KEY 的运行时间为 O (lg n )。

下面的 MAX-HEAP-INSERT 过程实现了 INSERT 操作。

MAX-HEAP-INSERT(A, key)
1 A.heap-size = A.heap-size + 1
2 A[A.heap-size] = -∞
3 HEAP-INCREASE-KEY(A, A.heap-size, key)