算法（C#版）堆

水深无声 2022-02-25 00:38 175阅读 0赞

**堆**

堆是具有下列性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于等于其左右孩子结点的值，称为小顶堆!

![20190331100446397.png][]

**堆排序**

堆排序算法就是利用堆（小顶堆或者大顶堆）进行排序的方法。

将待排序的序列构造成一个大顶堆，此时整个序列的最大值就是根节点。将它移走（跟堆的最后一个元素交换，此时末尾元素就是最大值），然后将剩余的n-1个序列重新构造成一个堆，这样就会得到n个元素中的次小值。如此反复执行，便能得到一个有序序列了。

![20190331100510236.png][]

![20190331100518745.png][]

**堆排序**

![20190331100533866.png][]

代码实现：分为两个函数，一个是用来调整大顶堆的，因为每次取出最大的数之后都要重新调整。另外一个是排序的函数。

using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;
    
    namespace 堆排序_顺序存储
    {
        class Program
        {
            static void Main(string[] args)
            {
                int[] data = { 50, 10, 90, 30, 70, 40, 80, 60, 20 };
                HeapSort(data);
                foreach (int i in data)
                {
                    Console.Write(i + " ");
                }
                Console.WriteLine();
                Console.ReadKey();
            }
    
            public static void HeapSort(int[] data)
            {
                for (int i = data.Length / 2; i >= 1; i--)//遍历这个数的所有非叶结点，挨个把所有的子树，变成子大顶堆
                {
                    HeapAdjust(i, data, data.Length);
                }
                //经过上面的for循环，把二叉树变成了大顶堆
    
                for (int i = data.Length; i > 1; i--)
                {
                    //把编号1和编号i位置进行交换
                    //1 到 (i-1)构造成大顶堆
                    int temp1 = data[0];
                    data[0] = data[i - 1];
                    data[i - 1] = temp1;
                    HeapAdjust(1, data, i - 1);
    
                }
            }
    
    
            private static void HeapAdjust(int numberToAdjust, int[] data, int maxNumber)
            {
                //把i结点的子树变成大顶堆
                int maxNodeNumber = numberToAdjust;//最大结点的编号
                int tempI = numberToAdjust;
                while (true)
                {
                    int leftChildNumber = tempI * 2;
                    int rightChildNumber = leftChildNumber + 1;
                    if (leftChildNumber <= maxNumber && data[leftChildNumber - 1] > data[maxNodeNumber - 1])
                    {
                        maxNodeNumber = leftChildNumber;
                    }
                    if (rightChildNumber <= maxNumber && data[rightChildNumber - 1] > data[maxNodeNumber - 1])
                    {
                        maxNodeNumber = rightChildNumber;
                    }
                    if (maxNodeNumber != tempI)//发现了一个比i更大的子结点，交换i和maxNodeNumber里面的数据
                    {
                        int temp = data[tempI - 1];
                        data[tempI - 1] = data[maxNodeNumber - 1];
                        data[maxNodeNumber - 1] = temp;
                        tempI = maxNodeNumber;
                    }
                    else
                    {
                        break;
                    }
                }
            }
        }
    }

结果为：

![20190331110903914.png][]

[20190331100446397.png]: /images/20220225/b78f1853dc33454b8f7f48bf97f99d73.png
[20190331100510236.png]: /images/20220225/8ce909594bcc49bab94745070e2344c2.png
[20190331100518745.png]: /images/20220225/2c534b50521a4d058e7bd1835a02e61b.png
[20190331100533866.png]: /images/20220225/c2f0d2e582f14596b88e00391a6d909d.png
[20190331110903914.png]: /images/20220225/c27b23a82edf4d17940dc12876447fee.png