关于堆排序中第二个循环的必要性及代码异常的技术问询

先看你提供的C#代码：

internal class Program
{
     static void Main(string[] args)
     {
         int[] arr = { 10, 40, 30, 20, 10, 5, 8 };
         int n = arr.Length;
         int i;

         heapsort(arr, n);

         Console.Write("\nAfter heap sort the array is:");
         for (i = 0; i < n; i++) { Console.Write(arr[i] + " "); }

         PriotrityQueue(arr, n);
         Console.Write("\nAfter deleting the item from priority queue the array is:");
         for (i = 0; i < n - 1; i++) { Console.Write(arr[i] + " "); }

         Console.ReadKey();
     }

     static void maxHeapify(int[] arr, int n, int i)
     {
         int large = i; //supposedly element with index i is maximum
         int left_child = 2 * i + 1;
         int right_child = 2 * i + 2;
         if (left_child < n && arr[left_child] > arr[large]) 
             large = left_child;
         if (right_child < n && arr[right_child] > arr[large])
             large = right_child;
         if (large != i)
         {
             int temp = arr[i];
             arr[i] = arr[large];
             arr[large] = temp;
             maxHeapify(arr, n, large);
         }
     }

     static void heapsort(int[] arr, int n)
     {
         for (int i = n - 1; i >= 0; i--) 
             maxHeapify(arr, n, i);
         for (int i = n - 1; i >= 0; i--) //this is the loop I do not understand
            {
                int temp = arr[0];
                arr[0] = arr[i];
                arr[i] = temp;
                maxHeapify(arr, i, 0);
            }
     }

     static void PriotrityQueue(int[] arr, int n)
     {
         if (n <= 0)
             return;
         arr[0] = arr[n - 1]; ;
         n--;
         maxHeapify(arr, n, 0);
     }
 }    

你的疑问点 #

• 移除heapsort内的第二个循环后，数组保持大顶堆结构，执行PriotrityQueue删除操作后得到符合预期的结果：30 20 8 10 10 5。
• 保留该循环时，堆排序后得到升序数组8 10 10 20 30 40，再执行删除操作得到40 8 10 10 20 30，不符合大顶堆的预期。
• 不理解这个循环的作用，以及为什么多数堆排序实现都包含它。

循环的作用与堆排序的逻辑 #

这个循环是堆排序的核心排序步骤，作用是把已经构建好的大顶堆转换成有序数组，具体逻辑如下：

1. 大顶堆的特性是arr[0]始终是整个堆的最大值。
2. 每次循环把堆顶的最大值（arr[0]）和当前堆的最后一个元素（arr[i]）交换，这样最大值就被放到了数组的末尾，成为有序部分的一员。
3. 交换后，堆的范围缩小（从0到i-1），此时堆顶元素可能不再满足大顶堆的特性，所以调用maxHeapify(arr, i, 0)重新调整堆结构，让剩余元素再次成为大顶堆。
4. 循环从后往前执行，直到整个数组都被排序，最终得到升序数组。

为什么你的场景保留循环会出问题 #

你的代码在堆排序后立刻执行了优先队列的删除操作，但此时数组已经是有序数组，不再是大顶堆结构了。PriotrityQueue方法的逻辑是基于大顶堆的（默认堆顶是最大值），所以在有序数组上执行这个方法，自然得不到符合大顶堆预期的结果。

简单来说：

• 如果你想要的是大顶堆结构（用于优先队列操作），只需要执行heapsort里的第一个循环（构建大顶堆），不需要第二个排序循环。
• 如果你想要的是排序后的数组，才需要执行第二个循环，把大顶堆转换成有序数组。

内容的提问来源于stack exchange，提问作者Ira