数据结构学习。最大堆。排序部分，第二个循环的必要性

Question

我们获得了代码：

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);
     }
 }    

代码（从我的角度来看）没有按预期工作。 如果我删除第二个循环，它会起作用：

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);
            }

我查看了不同的来源，他们使用了第二个循环而没有解释。我只是不明白为什么需要它。 没有它，我会收到正确的结果（再次来自我对最大堆的理解）： 从优先级队列中删除该项目后，数组为：30 20 8 10 10 5。

如果我使用循环，我会收到以下信息： 堆排序后，数组为 8 10 10 20 30 40 - 这只是一个按升序排序的数组 从优先级队列中删除该项目后，数组为：40 8 10 10 20 30 - 这是不对的

我只是想理解为什么这里使用第二个循环或者为什么它可以用于排序。 任何ide都值得赞赏。

Answer 1

请记住，最大的元素将位于堆的根部，即数组表示中的索引 0。第二个循环重复从位于索引 0 的堆中提取最大元素，并将其与数组中索引 i 处的最后一个未排序元素交换。然后，它通过堆化堆的其余部分来维护堆属性。在堆排序中，构建初始最大堆后，最大元素始终位于堆的根部（在数组表示中位于索引 0 处）。第二个循环本质上是通过重复从堆中提取最大元素（位于索引 0 处）、将其与最后一个未排序元素（位于索引 i 处）交换，然后对剩余堆进行堆化以维护堆属性来执行排序.

这对于堆排序算法很重要，因为它执行排序步骤。 当您执行优先级排队时似乎会出现问题。在这种情况下，您需要再次堆化数组以维护堆属性。