数据结构示例堆排序过程

悠悠 2022-04-18 02:33 170阅读 0赞

**分享一下我老师大神的人工智能教程！零基础，通俗易懂！[http://blog.csdn.net/jiangjunshow][http_blog.csdn.net_jiangjunshow]**

**也欢迎大家转载本篇文章。分享知识，造福人民，实现我们中华民族伟大复兴！**

完整算法见\[[例程][Link 1]\]，本文用一个例子，演示堆排序的过程。

例：对\{57, 40, 38, 11, 13, 34, 48, 75, 6, 19, 9, 7\}进行堆排序的过程。

算法如下:

void HeapSort(RecType R[],int n){    int i;    RecType temp;    //（1）循环建立初始堆    for (i=n/2; i>=1; i--)         sift(R,i,n);    //(2)进行n-1次循环,完成推排序    for (i=n; i>=2; i--)     {        temp=R[1];       //将第一个元素同当前区间内R[1]对换        R[1]=R[i];        R[i]=temp;        sift(R,1,i-1);   //筛选R[1]结点,得到i-1个结点的堆    }}
      
       
        1 
        2 
        3 
        4 
        5 
        6 
        7 
        8 
        9 
        10 
        11 
        12 
        13 
        14 
        15 
        16

（1）循环建立初始堆

for (i=n/2; i>=1; i--)         sift(R,i,n);
      
       
        1 
        2

用给出的序列构造堆的初始状态如下：  
![这里写图片描述][20151214150700559]  
在此基础上，根据上述代码，从最后一个分支节点开始调整，目标是得到大根堆。过程如下图：  
![这里写图片描述][20151214151444514]  
这个堆的存储结构是：  
![这里写图片描述][20151214152038974]

(2)进行n-1次循环,完成推排序

for (i=n; i>=2; i--)     {        temp=R[1];       //最大值交换到最后        R[1]=R[i];        R[i]=temp;        sift(R,1,i-1);   //前面的无序区调整为堆    }
      
       
        1 
        2 
        3 
        4 
        5 
        6 
        7

过程图示如下：  
![这里写图片描述][20151214154222367]  
请继续补充画完。

#### 给我老师的人工智能教程打call！[http://blog.csdn.net/jiangjunshow][http_blog.csdn.net_jiangjunshow] ####

![这里写图片描述][SouthEast]

[http_blog.csdn.net_jiangjunshow]: https://blog.csdn.net/jiangjunshow/article/details/77338485
[Link 1]: http://blog.csdn.net/sxhelijian/article/details/50118439
[20151214150700559]: /images/20220418/8e978bfc708b4f5283d9cfa6e928c526.png
[20151214151444514]: /images/20220418/ddf000d9152a43ea881143acb588096c.png
[20151214152038974]: /images/20220418/8efebe028c884b328592fea509798e5e.png
[20151214154222367]: /images/20220418/013709c730f9418fa7d5e114a9b67736.png
[SouthEast]: /images/20220418/088a69d9bdae45b5a564aa55ef64840b.png