[算法系列之一]堆排序

爱被打了一巴掌 2023-06-07 10:36 29阅读 0赞

前序：

(二叉)堆数据结构是一种数组对象，它可以被视为一棵完全二叉树。树中每个节点与数组中存放该节点值的那个元素对应。

树的每一层都是填满的，最后一层除外。

树的根为a\[1\] （在这里是从1开始的，也可以从0开始），给定了某个节点的下标i，其父节点为i/2，左二子为2\*i，右儿子为2\*i+1。

二叉堆满足二个特性：

1．父结点的键值总是大于或等于（小于或等于）任何一个子节点的键值。

2．每个结点的左子树和右子树都是一个二叉堆（最大堆或最小堆）。

当父结点的键值总是大于或等于任何一个子节点的键值时为最大堆。

当父结点的键值总是小于或等于任何一个子节点的键值时为最小堆。

![format_png][]

保持堆的性质：

MaxHeap是对最大堆进行操作的最重要的子程序。

以i为根的子树：

在算法每一步中，从a\[i\], a\[Left(i)\], a\[Right(i)\]找出最大值，并将其下标存在LargestIndex中。如果a\[i\]是最大的，则以i为根的子树已是最大堆,程序结束。

否则i的某个子结点中有最大元素则交换a\[i\],a\[LargetIndex\],从而使i及子女满足堆性质。下标为LargestIndex的结点在交换后的值为a\[i\],以该结点为根的子树又有可能违反最大堆的性质，因而又要对该子树递归调用MaxHeap，重新使子树平衡。

//调整以index为根的子树  
    //n：堆中元素个数  
    int MaxHeap(int a[],int index,int n){  
        int LargestIndex = index;  
        //左子节点  
        int LeftIndex = 2*index;  
        //右子节点  
        int RightIndex = 2*index+1;  
        if(LeftIndex <= n && a[LeftIndex] > a[LargestIndex]){  
            LargestIndex = LeftIndex;  
        }  
        if(RightIndex <= n && a[RightIndex] > a[LargestIndex]){  
            LargestIndex = RightIndex;  
        }  
        //如果a[index]是最大的，则以index为根的子树已是最大堆否则index的子节点有最大元素  
        //则交换a[index],a[LargetIndex],从而使index及子女满足堆性质  
        int temp;  
        if(LargestIndex != index){  
            //交换a[index],a[LargetIndex]  
            temp = a[index];  
            a[index] = a[LargestIndex];  
            a[LargestIndex] = temp;  
            //重新调整以LargestIndex为根的子树  
            MaxHeap(a,LargestIndex,n);  
        }  
        return 0;  
    }

建堆：

我们可以自底向上的用MaxHeap来将一个数组a\[1-n\]变成一个最大堆，子数组a\[n/2+1,........n\]中的元素是树中的叶子，因此每个都可以看做只含一个元素的堆，满足最大堆的要求，不用调整。所以只需调整以a\[n/2........1\]中元素为根的子树使之成为最大堆。

//建堆：将一个数组a[1-n]变成一个最大堆  
    int BuildMaxHeap(int a[],int n){  
        int i;  
        //子数组a[(n/2+1,n/2+2......n)]中的元素都是树中的叶子  
        for(i = n/2;i >= 1;i--){  
            //调整以i为根节点的树使之成为最大堆  
            MaxHeap(a,i,n);  
        }  
        return 0;  
    }

a数组

初始堆：

![format_png 1][]

自底向上从最后一个非叶节点开始调整：

![format_png 2][]![format_png 3][]![format_png 4][]

![format_png 5][]

每次调整都是从父节点、左孩子节点、右孩子节点三者中选择最大者跟父节点进行交换(交换之后可能造成被交换的孩子节点不满足堆的性质，因此每次交换之后要重新对被交换的孩子节点进行调整)。

堆排序：

开始时，堆排序先用BuildMaxHeap将输入数组a\[1-n\]构造成一个最大堆。又因为数组中最大元素在根a\[1\]，则可以通过它与a\[n\]交换来达到最终的正确位置。现在，如果从堆中”去掉“结点n(不是真的删除，而是通过修改堆的元素个数n)，可以很容易的将a\[1-(n-1)\]建成最大堆。原来根的子女依旧是最大堆，二新交换的根元素很有可能违背最大堆的性质。这时调用MaxHeap重新调整一下。在a\[1-(n-1)\]中构造出最大堆。堆排序不断重复这一过程，堆的大小由n-1一直降到2.从而完成排序的功能

//堆排序  
    int HeapSort(int a[],int n){  
        int temp;  
        //BulidMaxHeap将输入数组构造一个最大堆  
        BuildMaxHeap(a,n);  
        //数组中最大元素在根a[1]，则可以通过它与a[n]交换来达到最终的正确位置  
        for(int i = n;i >= 2;i--){  
            //交换  
            temp = a[i];  
            a[i] = a[1];  
            a[1] = temp;  
            //a[i]已达到正确位置，从堆中去掉  
            n--;  
            //重新调整，保持最大堆的性质  
            MaxHeap(a,1,n);  
        }  
        return 0;  
    }

![format_png 6][]![format_png 7][]![format_png 8][]![format_png 9][]

![format_png 10][] ![format_png 11][]![format_png 12][]![format_png 13][]![format_png 14][]![format_png 15][]![format_png 16][]

红色为排序后的结果；

代码：

#include<stdio.h>  
    #include<stdlib.h>  
      
    //调整堆  
    int MaxHeap(int a[],int index,int n){  
        int LargestIndex = index;  
        //左子节点  
        int LeftIndex = 2*index;  
        //右子节点  
        int RightIndex = 2*index+1;  
        if(LeftIndex <= n && a[LeftIndex] > a[LargestIndex]){  
            LargestIndex = LeftIndex;  
        }  
        if(RightIndex <= n && a[RightIndex] > a[LargestIndex]){  
            LargestIndex = RightIndex;  
        }  
        //如果a[index]是最大的，则以index为根的子树已是最大堆否则index的子节点有最大元素  
        //则交换a[index],a[LargetIndex],从而使index及子女满足堆性质  
        int temp;  
        if(LargestIndex != index){  
            //交换a[index],a[LargetIndex]  
            temp = a[index];  
            a[index] = a[LargestIndex];  
            a[LargestIndex] = temp;  
            //重新调整以LargestIndex为根的子树  
            MaxHeap(a,LargestIndex,n);  
        }  
        return 0;  
    }  
      
      
    //建堆：将一个数组a[1-n]变成一个最大堆  
    int BuildMaxHeap(int a[],int n){  
        int i;  
        //子数组a[(n/2+1,n/2+2......n)]中的元素都是树中的叶子  
        for(i = n/2;i >= 1;i--){  
            //调整以i为根节点的树使之成为最大堆  
            MaxHeap(a,i,n);  
        }  
        return 0;  
    }  
      
    //堆排序  
    int HeapSort(int a[],int n){  
        int temp;  
        //BulidMaxHeap将输入数组构造一个最大堆  
        BuildMaxHeap(a,n);  
        //数组中最大元素在根a[1]，则可以通过它与a[n]交换来达到最终的正确位置  
        for(int i = n;i >= 2;i--){  
            //交换  
            temp = a[i];  
            a[i] = a[1];  
            a[1] = temp;  
            //a[i]已达到正确位置，从堆中去掉  
            n--;  
            //重新调整，保持最大堆的性质  
            MaxHeap(a,1,n);  
        }  
        return 0;  
    }  
    int main(){  
        int n = 6;  
        //a[0]不用，堆的根结点是从1开始的  
        int a[] = {0,3,17,8,7,16,20};  
        HeapSort(a,n);  
        for(int i = 1;i <= n;i++){  
            printf("%d ",a[i]);  
        }  
        return 0;  
    }

本文原文地址：[https://blog.csdn.net/SunnyYoona/article/details/24741371][https_blog.csdn.net_SunnyYoona_article_details_24741371]

[format_png]: /images/20230601/289ed7f84f544e1bb9648be5a20b213c.png
[format_png 1]: /images/20230601/78aff236f1c24bbda28f2af56f8a333f.png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWctbXkuY3Nkbi5uZXQvdXBsb2Fkcy8yMDEzMDIvMjMvMTM2MTYyODk5MF8yMDQ3LmpwZw?x-oss-process=image/format,png
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWctbXkuY3Nkbi5uZXQvdXBsb2Fkcy8yMDEzMDIvMjMvMTM2MTYyOTA4N180NTQyLmpwZw?x-oss-process=image/format,png
[format_png 4]: /images/20230601/cb6df386b0bb4f9a8ec4bd6c75a8f806.png
[format_png 5]: /images/20230601/291afa1285474be1b0df08dc3d7cd356.png
[format_png 6]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWctbXkuY3Nkbi5uZXQvdXBsb2Fkcy8yMDEzMDIvMjMvMTM2MTYzMDA4NF85MDI4LmpwZw?x-oss-process=image/format,png
[format_png 7]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWctbXkuY3Nkbi5uZXQvdXBsb2Fkcy8yMDEzMDIvMjMvMTM2MTYzMDEzMF80MjI0LmpwZw?x-oss-process=image/format,png
[format_png 8]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWctbXkuY3Nkbi5uZXQvdXBsb2Fkcy8yMDEzMDIvMjMvMTM2MTYzMDE4M183MDQ3LmpwZw?x-oss-process=image/format,png
[format_png 9]: /images/20230601/cf00bb1a0ade4f36bd171b213ab27617.png
[format_png 10]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWctbXkuY3Nkbi5uZXQvdXBsb2Fkcy8yMDEzMDIvMjMvMTM2MTYzMDI1OV80MDMwLmpwZw?x-oss-process=image/format,png
[format_png 11]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWctbXkuY3Nkbi5uZXQvdXBsb2Fkcy8yMDEzMDIvMjMvMTM2MTYzMDMwOV8xMzMyLmpwZw?x-oss-process=image/format,png
[format_png 12]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWctbXkuY3Nkbi5uZXQvdXBsb2Fkcy8yMDEzMDIvMjMvMTM2MTYzMDMzOF8yNTc5LmpwZw?x-oss-process=image/format,png
[format_png 13]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWctbXkuY3Nkbi5uZXQvdXBsb2Fkcy8yMDEzMDIvMjMvMTM2MTYzMDM3M182NjUwLmpwZw?x-oss-process=image/format,png
[format_png 14]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWctbXkuY3Nkbi5uZXQvdXBsb2Fkcy8yMDEzMDIvMjMvMTM2MTYzMDQ0MF8yMTA0LmpwZw?x-oss-process=image/format,png
[format_png 15]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWctbXkuY3Nkbi5uZXQvdXBsb2Fkcy8yMDEzMDIvMjMvMTM2MTYzMDQ3OF80Mzc2LmpwZw?x-oss-process=image/format,png
[format_png 16]: /images/20230601/0ae232d9cc484b66b9757c0c5d301c94.png
[https_blog.csdn.net_SunnyYoona_article_details_24741371]: https://blog.csdn.net/SunnyYoona/article/details/24741371