首页 C&C++ 数据结构与算法分析

# 编写在二叉堆中进行上滤和下滤的例程

这是二叉堆的最重要操作步骤。

上滤波
static int percolateUp(BinHeap H, BinHeapElementType X, int Pos)
{   
    int i;
    for(i= Pos;H->Elements[i/2]>X;i/=2)
      H->Elements[i] = H->Elements[i/2];
    
    return i;
}
下滤波
static int percolateDown(BinHeap H, BinHeapElementType LastElement, int Pos)
{
    int i, Child;
    for(i = Pos; 2*i <= H->Size; i = Child)
    {
        Child = 2*i;
        if(Child != H->Size && H->Elements[Child + 1] 
                                < H->Elements[Child])
           Child++;
        
        if(LastElement > H->Elements[Child])
           H->Elements[i] = H->Elements[Child];
        else
           break;
    }
    return i;
}
# 写出并测试一个在二叉堆中执行 Insert，DeleteMin，BuildHeap，FindMin，DecreaseKey，Delete 和 IncreaseKey 等操作的程序
说白了就是叫你写一个数组的完全二叉树。
BinHeap BinHeapInit(int MaxSize)
{
    BinHeap H = malloc(sizeof(Binheap));
    H->Elements = malloc(sizeof(BinHeapElementType) * (MaxSize+1));
    H->Capacity = MaxSize;
    H->Size = 0;
    H->Elements[0] = NONUM;
    return H;
}
bool BinHeapIsFull(BinHeap H)
{
    return H->Size == H->Capacity;
}
void BinHeapInsert(BinHeap H, BinHeapElementType X)
{
    if(BinHeapIsFull(H))
    {
        printf("BinHeap if full\n");
        return ;
    }
    H->Size++;
    int pos = percolateUp(H, X, H->Size); 
    H->Elements[pos] = X;
}
static int percolateUp(BinHeap H, BinHeapElementType X, int Pos)
{   
    int i;
    for(i= Pos;H->Elements[i/2]>X;i/=2)
      H->Elements[i] = H->Elements[i/2];
    
    return i;
}
bool BinHeapIsEmpty(BinHeap H)
{
    return H->Size == 0;
}
BinHeapElementType BinHeapDeleteMin(BinHeap H, int Pos)
{
    if(BinHeapIsEmpty(H))
    {
        printf("BinHeap is empty\n");
        return H->Elements[0];
    }
    BinHeapElementType MinElement = H->Elements[Pos];
    BinHeapElementType LastElement = H->Elements[H->Size--];
    int i = percolateDown(H,LastElement, Pos);
    H->Elements[i] = LastElement;
    return MinElement;
}
static int percolateDown(BinHeap H, BinHeapElementType LastElement, int Pos)
{
    int i, Child;
    for(i = Pos; 2*i <= H->Size; i = Child)
    {
        Child = 2*i;
        if(Child != H->Size && H->Elements[Child + 1] 
                                < H->Elements[Child])
           Child++;
        
        if(LastElement > H->Elements[Child])
           H->Elements[i] = H->Elements[Child];
        else
           break;
    }
    return i;
}
void BinHeapPrint(BinHeap H)
{
    for(int i = 1; i <= H->Size; i++)
       printf("%d ", H->Elements[i]);
    printf("\n");
}
BinHeapElementType BinHeapFindMin(BinHeap H)
{
    if(BinHeapIsEmpty)
    {
        printf("Heap is empty\n");
        return H->Elements[0];
    }
    return H->Elements[1];
}
BinHeap BinHeapDestory(BinHeap H)
{
    free(H->Elements);
    free(H);
    return NULL;
}
int BinHeapDecraseKey(BinHeap H, int Offset, int Pos)
{
    int i;
    if(Offset == NONE || Offset >= H->Elements[Pos])
       return Pos;
    else
    {
        H->Elements[Pos] -= Offset; 
        BinHeapElementType LastElement = H->Elements[Pos];
        i = percolateUp(H,LastElement,Pos);
        if(i != Pos) H->Elements[i] = LastElement;
    }
    return i;
}
void BinHeapIncreaseKey(BinHeap H, int Offset, int Pos)
{
    H->Elements[Pos] += Offset;
    BinHeapElementType LastElement = H->Elements[Pos];
    int i = percolateDown(H, LastElement, Pos);
    if(i != Pos) H->Elements[i] = LastElement;
}
void BinHeapDelete(BinHeap H, int Pos)
{
    int pos = BinHeapDecraseKey(H, NONE,Pos);
    BinHeapDeleteMin(H, Pos);
}
void BinHeapBuildHeap(BinHeap H)
{
    int N = H->Size, pos = 0;
    BinHeapElementType LastElement;
    for(int i = N/2; i > 0; i--)
    {
        LastElement = H->Elements[i];
        pos = percolateDown(H,LastElement, i);
        if(pos != i) H->Elements[pos] = LastElement;
    }
}
# 习题 6.7
# a. 证明对于二叉堆，BuildHeap 至多在元素间进行 2N-2 次比较
对二叉树，可知高度 h 上有 1 个节点、高度 h-1 有 2 个节点等以及一般的在高度 h-i 上的2i2^{i} 个节点组成，则所有节点的高度的和为
S=∑i=0h=h+2(h−1)+4(h−2)+...2h−1S= {\textstyle \sum_{i=0}^{h}} = h +2(h-1)+4(h-2)+...2^{h-1}
两边乘于 2 得
2S=∑i=0h=2h+4(h−1)+8(h−2)+...2h2S= {\textstyle \sum_{i=0}^{h}} = 2h +4(h-1)+8(h-2)+...2^{h}
使用错位相减法得
S=−h+2+4+8+...+2h−1+2h=(2h+1+1)−(h+1)S=-h+2+4+8+...+2^{h-1}+2^h=(2^{h+1}+1)-(h+1)
BuildHeap 得时间界可以通过计算堆中所有节点高度得知，即上式。
假设二叉堆有 N 个节点，令h=log⁡Nh=\log_{}{N}, 则S=2N−2−log⁡NS =2N-2-\log_{}{N}
当 N=0 或 N=1 以级 N 很大时，可以忽略令log⁡N\log_{}{N}, 所以 BuildHeap 至多在元素间进行 2N-2 次比较。
# b. 证明 8 个元素的堆可以通过堆元素间的 8 次比较构成。
假设已有一个预排序得数组，经过左堆得插入例程则需要 N 次比较，所以插入次数N≥7N\ge7，即 8 个元素的堆可以通过堆元素间的 8 次比较构成。
# c. 给出一个算法用138N+O(logN)\frac{13}{8}N+O(logN) 次元素比较构建出一个二叉堆
先递归生成一个二项队列，然后遍历合并成二叉堆。
# 证明，在一个大的完全堆 (你可以假设N=2k−1N=2^k-1) 中第 k 个最小元的期望深度以log⁡k\log_{}{k} 为界。
对于k>1,E(Dk)=∑j=1k−1pj,k(E(Dj)+1)k>1,E(D_k)= {\textstyle \sum_{j=1}^{k-1}} p{j,k}(E(D_j)+1)
其中DkD_k 表示第 K 个最小深度得随机变量，pj,kp{j,k} 是第 K 个最小深度随机变量得概率。
又因为pj,k=pk−1j,k=12k−2(k−2j−1)p{j,k} = p{k-1j,k} = \frac{1}{2^{k-2}}\binom{k-2}{j-1}
所以总式子E(Dj)+E(Dk−j)≤log⁡j+log⁡k−jE(D_j)+E(D{k-j})\le \log_{}{j}+ \log_{}{k-j}
又因为log⁡j+log⁡k−j≤2log⁡k/2\log_{}{j}+\log_{}{k-j}\le 2\log_{}{k/2},pj,k=pk−j,kp_{j,k} = p_{k-j,k}
两边相乘pj,k=pk−j,kp_{j,k} = p_{k-j,k} 并变化得
pj,kE(Dj)+pk−j,kE(Dk−j)≤pj,klog⁡k/2+pk−j,klog⁡k/2p_{j,k}E(D_j)+p_{k-j,k}E(D_{k-j})\le p_{j,k}\log_{}{k/2} +p_{k-j,k}\log_{}{k/2}
对于定理有E(Dk)=1+∑j=1k−1pj,k(E(Dj)+1)E(D_k)=1+ {\textstyle \sum_{j=1}^{k-1}} p_{j,k}(E(D_j)+1)
其中E(Dk)≤1+∑j=1k−1pj,klog⁡k/2≤l+log⁡k/2≤log⁡kE(D_k)\le 1+ {\textstyle \sum_{j=1}^{k-1}} p_{j,k} \log{}{k/2}\le l+\log{}{k/2}\le\log{}{k}
所以第 k 个最小元的期望深度以log⁡k\log_{}{k} 为界。
我都不知道这个我写得是啥，呜呜呜。
# 如果一个 d - 堆作为一个数组存储，那么对位于位置 i 的项，其父亲和儿子都在哪里？
父亲:(i+d−2)/d(i+d-2)/d
儿子:(i+1)d+2,...id+1(i+1)d+2,...id+1
# 设一个 d - 堆初始时有 N 个元素，而我们需要对其执行 M 次 PerolateUP 和 N 次 DeleteMin.
a. 用 M，N 和 d 表示的所有操作的总的运行时间是多少？
b. 如果 d=2，所有的堆的操作的运行时间是多少？
c. 如果 d=Θ（N）d=Θ（N）, 总的运行时间是多少？
d. 对 d 作什么选择将最小化总的运行时间
a:O((M+dN)log⁡dN)O((M+dN)\log{_d}{N})
b:O((M+N)log⁡N)O((M+N)\log{}{N})
c:O((M+N2))O((M+N^2))
d:d=max(2,M/2)d = max(2,M/2)
# 习题 6.20
# a. 左式堆能否有效的支持 DecreaseKey？
# b. 完成该功能需要哪些变化（如果可能的话）？
能，但还使用二叉堆常规得上滤操作就麻烦了，对大数据尤其无力，但是插入和删除操作是很方便得，所以可以通过先删除值后把值后面得子树插入就可以快速得实现 DecreaseKey 操作了，具体代码实现看这里。
# 我们可以以线性时间对左式堆执行 BuildHeap 操作：把每个元素当做是单节点左式堆，把所有这些堆放到一个队列中。之后，让两个堆出队，合并它们，再将合并的结果入队，直到队列中只有一个堆为止。其中，BuildHeap 表示构建堆 ，BuildHeap (H) 操作把 N 个关键字作为输入并把它们放到空堆中。
a. 证明该算法在最坏情形下为 O (N)。
b. 为什么该算法优于下面的算法
当第一次队列合并时，有 2 个元素出队，N/2 次合并，1 次比较 (该树只有一个元素)；
当第二次队列合并时，有 2 个元素出队，N/4 次合并，2 次比较 (该树只有两个元素)；
同理，当第 n 次队列合并时，有 2 个元素出队，N/2*n 次合并，n 次比较 (该树只有两个元素)。
所以可归纳公式为
S=2∗1∗N2+2∗2∗N4+2∗3∗N8+...2∗n∗N2nS = 2*1*\frac{N}{2}+2*2*\frac{N}{4}+2*3*\frac{N}{8}+...2*n*\frac{N}{2n}
取前 n 个值，可近似得到S≥3NS\ge 3N
所以该算法最坏情形为 O (N), 且该算法较常规插入能产生更倾斜得左式堆，性能更好。
# 证明二项树BkB_k 以二项树B0B_0,B1B_1, ... Bk−1B_{k-1} 作为其根的儿子
已知对于二项树BkB_k，有节点数2k=2k+1+2k+12_k=2_{k+1}+2_{k+1}
假设该假设成立，对 k=0,1, 明显成立
对于 k=2, 有22=21+21=21+20+12^2=2^1+2^1=2^1+2^0+1
对于 k=3, 有23=22+22=22+21=22+21+20+12^3=2^2+2^2=2^2+2^1=2^2+2^1+2^0+1
所以对于 k, 有2k=2k−1+2k−2+....20+12^k=2^{k-1}+2^{k-2}+....2^0+1 依旧成立
则对于 k+1, 有2k+1=2k+2k=2k+2k−1+2k−2+....20+12^{k+1}=2^{k}+2^{k}=2^{k}+2^{k-1}+2^{k-2}+....2^0+1
所以二项树BkB_k 以二项树B0B_0,B1B_1, ... Bk−1B_{k-1} 作为其根的儿子成立。
# 证明高度为 k 的二项树在深度 d 有(nd)\binom{n}{d} 个节点。
首先，二项式系数(kd)=k!d!(k−d)!\binom{k}{d}=\frac{k!}{d!(k-d)!}
假设该结论成立
对于 k=0，(0d)=0!d!(0−d)!=1\binom{0}{d}=\frac{0!}{d!(0-d)!}=1
k=1,(2d)=2!d!(2−d)!\binom{2}{d}=\frac{2!}{d!(2-d)!}
对于 k 依旧成立，(kd)=k!d!(k−d)!\binom{k}{d}=\frac{k!}{d!(k-d)!}
则对于 k+1 时，有(k+1d)=(k+1)!d!(k+1−d)!=k+1(k+1−d)!(kd)\binom{k+1}{d}=\frac{(k+1)!}{d!(k+1-d)!}=\frac{k+1}{(k+1-d)!}\binom{k}{d}, 假设成立。
# 习题 6.30
# a. 证明：向初始为空的二项队列进行 N 次 insert 最坏情形下的运行时间为 O (N)
插入过程中，各有 N 次 insert、compare、merge 过程，总计 3N，所以最坏情形为 O (N)。
# b. 给出一个算法来建立有 N 个元素的二项队列，在元素间最多使用 N-1 次比较。
在标准插入例程中加入一个标志位表示B0B_0, 可以减少一次比较，所以最终有 N-1 次比较。
# 设我们想要将操作 DecreaseAllKeys (△\bigtriangleup) 添加到堆的指令系统中去。该操作的结果是堆中所有的关键字都将它们的值减少量△\bigtriangleup。对于你所选择的堆的实现方法，解释所做的必要的修改，使得所有其他操作都保持它们的运行时间而 DecreaseAllKeys 以 O (1) 运行
堆不能直接保留键值，实际保留只有父节点的值且不在堆中，堆中保留的实际时各节点值与父节点值得插值，这样 DecreaseAllKeys 得操作就是 O (1) 的，而其它操作时间界不变。
# 这两个选择算法中哪个具有更好的时间界？
第一种选择算法总运行时间为S1=O(N+klog⁡N)S_1=O(N+k\log{}{N}), 第二种选择算法总的运行时间为S2=O(Nlog⁡k)S_2=O(N\log{}{k})。
总体上第一种优于第二种，但也不是绝对的，取决于 k。
当k=O(N/log⁡N)k=O(N/\log{}{N}),S1>S2S_1>S_2, 当k=O(N)k=O(N),S1=S2S_1=S_2。