数据结构与算法——堆排序

心已赠人 2022-08-24 11:58 147阅读 0赞

## 堆排序 ##

前面的博文[《二叉堆》][Link 1]已经对二叉堆介绍了，在这里不再多介绍，堆排序主要是利用堆的性质，相当于删除根节点元素之后，再对堆进行调整，使其成为新的二叉堆。

/**堆排序**/
    /**堆排序,就要先了解下二叉堆这种数据结构。
    
    二叉堆
        二叉堆其实是一棵有着特殊性质的完全二叉树，这里的特殊性质是指：
    
        1、二叉堆的父节点的值总是大于等于（或小于等于）其左右孩子的值；
    
        2、每个节点的左右子树都是一棵这样的二叉堆。
    
        如果一个二叉堆的父节点的值总是大于其左右孩子的值，那么该二叉堆为最大堆，反之为最小堆。
        我们在排序时，如果要排序后的顺序为从小到大，则需选择最大堆，反之，选择最小堆，这点通过后面对堆排序分析，
        你会有所体会。
    
    堆排序
        由二叉堆的定义可知，堆顶元素（即二叉堆的根节点）一定为堆中的最大值或最小值，因此如果我们输出堆顶元素后，
        将剩余的元素再调整为二叉堆，继而再次输出堆顶元素，再将剩余的元素调整为二叉堆，反复执行该过程，
        这样便可输出一个有序序列，这个过程我们就叫做堆排序。
    
    
        调整二叉堆
        /**调整最大堆，二叉堆的根结点序号为root=0,左右子树的结点分别为2*root+1,2*root+2**/
        void HeapAdjust(int *arr,int root,int End)
        {
            int temp=arr[root];//保存当前结点
            int k=2*root+1;//该结点的左子树结点的位置
            while(k<=End)
            {
                if(k<=End-1 && arr[k+1]>arr[k])//类似层次遍历,找出左右子树最大的数据
                    k++;
                if(arr[k]<=temp)
                    break;
                else
                {
                    arr[root]=arr[k];//最大子结点向上移,替换其父节点
                    root=k;//把子节点作为当前结点
                    k=2*root+1;
                }
            }
            arr[root]=temp;
        }
        void Heap_sort(int *arr,int len)
        {
            int i;
            int temp;
            //把数组建成为最大堆
            //第一个非叶子节点的位置序号为(len-1)/2
            for(i=(len-1)/2;i>=0;i--)
                HeapAdjust(arr,i,len);
            //堆排序
            for(i=len-1;i>0;i--)
            {
                //堆顶数据和最后数据交换
                SWAP(arr[0],arr[i],temp);
                HeapAdjust(arr,0,i-1);//重新调整最大堆
                //show(arr,len);
               // printf("\n");
            }
        }

[Link 1]: http://blog.csdn.net/chenhanzhun/article/details/21086973