6 Heapsort

未分类

---

介绍

堆排序的优点，时间上和归并排序一样，同时像插入排序一样，每次只有一个待排序的元素进行排序。
在这里用到了数据结构，在这里还是叫“heap”。（an efficient priority queue？）
"heap"也指"harbage-collect storage",如同java和lisp提供的那样。（？）
但是我们这里不是，仅仅是一个数据结构。

6.1 Heaps

这里提到的堆是完树的结构（除了最底层的节点，每个节点的叶子都是满的，把数组从左开始填进去）。每一个节点都反应了数组里的一个元素。一个反应堆的数组有以下两个数据，一个是A.length一个是A.heap-size，长度定义了有多少个元素，size表示有多少个元素是已经排好序的（说他们是有效的）。根节点叫做A[1],给每个节点一个下标i，我们可以轻易地算出左孩子、右孩子、根（的下标）。
用圈圈圈起来的数字是这个节点的值，上面是下标，数组上的弧线表示了母与孩子的关系。树的最下面是第0层，往上递增。
传进一个下标i，怎么求他的母、左右孩子的下标。在计算计中可以通过位移来完成，这里不赘述。

两种堆

第一种，他的根节点永远比左右孩子大，另一种就是小。分别叫最小堆和最大堆。
定义节点和堆的高度，节点的高度是从这个节点到离他最远的叶子的高度，堆的高度就是根节点的高度。如果这个树是一个完树，有n个元素，那么他有lg n层。
最大堆（满）程序遍历要O（lg n）的时间，是维护最大堆的关键。
建一个堆要线性的时间（？）把一个未排序的数组塞进树里去。
排序时间是O（lg n）
最大堆插入......都是O（lg n），使堆数据结构可以实施公共性队列。

void sort1(int A[],int len,int i){//堆排序的6.1伪代码实现，只针对除了根节点其他都已经排好序的情况
    int l=i*2;//length表示数组的长度
    int r=i*2+1;//A.heap-size堆中有多少个元素存在数组A中，i*2乘下去会。。。
    int largest;
    int temp=0;
    if(i>=len)
        return;
    if(l<len&&A[i]<A[l]){
        largest=l;
    }
    else{
        largest=i;
    }
    if(r<len&&A[largest]<A[r])
        largest=r;
    if(i!=largest){
        temp=A[i];
        A[i]=A[largest];
        A[largest]=temp;
    }
    sort1(A,len,largest);
}

6.1-2怎么证明他的高度呢？

6.2维护堆的特性

首先，放入一个数组和他的下标i，假设这个树的根的左孩子和右孩子的树都是最大堆，但是A[i]一定比他的孩子小，因此破坏了堆的特性？。这个程序让A[i]在堆中下滑，子树的根在下标i遵循了这种规律。
解释一下伪代码，首先传入根节点，算出左右孩子的下标l、r，如果l小于已排序的元素的个数而且左孩子比根节点要大，就让largest等于左孩子的下标，否则等于根的下标。如果是然后将右孩子用相同方法比较一次。假如最后largest不等于根节点的下标，就置换根节点和这个下标（largest）代表的节点，再将largest下标进行递归。（A.heap-size）递归的原因是如果进行了交换，就会导致下面的节点不符合最大堆的规则。而根据一开始的设定，没有置换的那一边都是排好的。
如果一个有n层的子树最上面的节点是i，用$\theta(1)$的时间来安顿左右和根的关系。加上在该子树i节点的一个孩子上运行（假设这个发生了）。孩子的每一个子树的规模都是2n/3，最坏的情况是树的最底层是半满的（？）。于是我们就能描述运行这个程序的时间：

$$T(n)<=T(2n/3)+\theta(1)$$
可得结果是T(n)=O(lg n),我们也可以说在一个高度为h的节点运行时间是O(h).(lg n?)

void BuildAHeap(int A[],int len){//将第一层的节点都丢进去，实现对每一个节点的排序
    for(int i=len/2;i>0;i--){
        sort1(A,len,i);
    }
}

6.3 建一个堆

我们可以用程序Max-HEAPIFY这种从底到顶的方式来转换数组A，堆有n个元素。A[(n/2(下取))+1]都是树的叶子，都可以看成一个元素的堆。
这个程序从倒数第二层开始（最下面都是1，没得搞啦），将数组的长度除2，算出来这个元素在堆中对应的父节点，根据前面二叉树的下标，从数组长度除二开始到1的所有下标，代表的节点都有左右孩子。把这些节点依次丢到上一个程序去排序。最后会得到一个最大堆。
不变量是什么？表示不变量真的在第一次迭代里是优先的，每一次的迭代都保持不变量，不变量在终结的时候会提供一个有用的财产来表示正确性。
初始化：优先考虑循环的第一次迭代，把每个节点送进去（说起来为什么要叫初始化？）
保持：可以看到每一次循环都保持了不变量，观察i的孩子的标记比i高，这是Max-HEAPIFY能运行的要求。
终结：i=0；。
接下来算该程序的最大运行时间。每一个Max-HEAPIFY都是O（lg n），build是O（n），所以总的就是O（n lg n），并不是渐进的。
测试这个程序的时间只要改变节点的高度来测试。（大多数的高度都是小的？）
tighter analysis6.1-2,6.3-3去证明一下，
这个程序的时间也是O（h）.

void Heapsort(int A[],int len){
    int temp;
    BuildAHeap(A,len);
    for(int i=len;i>1;i--){
        temp=A[1];
        A[1]=A[i];
        A[i]=temp;
        len-=1;
        sort1(A,len,1);
    }
    }