《算法导论》第六章习题选做

6.1-7证明：当用数组表示储存n个元素的堆时，叶节点下标分别是[n/2]+1,[n/2]+2,...,n。
证：如图所示

堆的最后两行中n/2节点以后的节点全是叶，得证。
6.2-5Max-Heapify代码效率较高，但第10行中的递归调用可能例外，它可能使某些编译器产生低效的代码。请用循环控制结构取代递归，重写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
    while i <= n and largest != i
        exchange A[i] with A[largest]a
        i = largest
        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

6.5-8Heap-Delete(A, i)操作能够将节点i从堆A中删除。对于一个包含n个元素的堆，请设计一个能够在O（lgn）时间内完成的Heap-Delete操作。

Heap-Delete(A, i)
    A[i] = -∞
    Max-Heapify(A, i)

6.5-9请设计一个时间复杂度为O（nlgk)的算法，它能够将k个有序链表合并为一个有序链表，这里n时所有输入链表的总的元素个数。（提示：使用最小堆来完成k路合并。）
最开始想到直接连接然后快排，但时间复杂度为O（nlgn），明显k $图片说明$ n,因此此方法不合题意。
由于有序链本身就是最小堆，因此将k个堆中的最小值取出并删除，然后用Min-Heapify构建新堆，依次进行，时间复杂度为O（nlgk）.

Merge-klines(A) //A表示k个最小堆
    i = 1
    while i <= n
        min = Find-Min(A)
        Min-Heapify(A, i)
        i = i + 1

C++代码如下：

#include<iostream>
#include<vector>
using namespace std;
vector<int> k;
int a[10][10] = {{0, 2, 3, 4, 0x3f3f3f3f}, {0, 1, 7, 9, 11, 0x3f3f3f3f}, {0, 12, 63, 92, 0x3f3f3f3f}}, n, size[4] = {4, 5, 4}, sum=0, num;
int parent(int i) //叫爸爸 
{
    return i / 2;
}
int left(int i) //左儿子 
{
    return i * 2;
}
int right(int i) //右儿子 
{
    return i * 2 + 1;
}
void Min_Heapify(int a[], int i, int x) //让爸爸最小 
{
    int l = left(i);
    int r = right(i);
    int largest = 0;
    if(l <= size[x] && a[l] < a[i])
        largest = l;
    else
        largest = i;
    if(r <= size[x] && a[r] < a[largest])
        largest = r;
    if(largest != i)
    {
        swap(a[i], a[largest]);
        Min_Heapify(a, largest, x);
    }
}
int Find_Min(void)
{
    int mine = 0x3f3f3f3f, flag = 1;
    for(int i = 0; i < num; i++)
    {
        if(mine > a[i][1])
        {
            mine = a[i][1];
            flag = i;
        }
    }
    return flag;
}
void Merge_klines(void)
{
    int i = 1;
    while(i <= n)
    {
        int mine = Find_Min();
        k.push_back(a[mine][1]);
        swap(a[mine][1], a[mine][si***e]]);
        si***e]--;
        Min_Heapify(a[mine], 1, mine);
        i++;
    }
}
int main()
{
    n = 10, num = 3;
    Merge_klines();
    for(int i = 0; i < n; i++)
        cout<<k[i]<<" ";
    return 0;
}

运行结果如下：
图片说明