堆排序是计算机编程中一种流行且高效的排序算法。学习如何编写堆排序算法需要了解两种类型的数据结构：数组和树。

我们要排序的初始数字集存储在一个数组中，例如 [10, 3, 76, 34, 23, 32]，排序后，我们得到一个已排序的数组[3,10,23,32,34,76]。堆排序的工作原理是将数组的元素可视化为一种特殊的完整二叉树，称为堆。
注意：作为先决条件，您必须了解完整的二叉树和堆数据结构。

数组索引与树元素

完整的二叉树有一个有趣的特性，我们可以用它来找到任何节点的子节点和父节点。如果数组中任何元素的索引是 i，索引中的元素 2i+1 将成为左孩子，2i+2 索引中的元素将成为右孩子。此外，索引处任何元素的父元素 i 由的下界给出 (i-1)/2。


数组和堆索引之间的关系

理解数组索引到树位置的这种映射对于理解堆数据结构如何工作以及如何使用它来实现堆排序至关重要。

子节点索引位置的计算 ```bash Left child of 1 (index 0) = element in (2*0+1) index = element in 1 index = 12

Right child of 1 = element in (2*0+2) index = element in 2 index = 9

Similarly, Left child of 12 (index 1) = element in (2*1+1) index = element in 3 index = 5

Right child of 12 = element in (2*1+2) index = element in 4 index = 6


- 父节点索引位置的计算
```bash
Parent of 9 (position 2) 
= (2-1)/2 
= ½ 
= 0.5
~ 0 index 
= 1
Parent of 12 (position 1) 
= (1-1)/2 
= 0 index 
= 1

什么是堆数据结构

堆是一种特殊的基于树的数据结构。如果满足以下条件，则称二叉树遵循堆数据结构。它是一棵完整的二叉树。

树中的所有节点都遵循它们大于其子节点的属性，即最大的元素位于根及其子节点处，并且小于根等等。这样的堆称为最大堆。如果相反，任意节点都小于它们的子节点，则称为最小堆。下面的示例图显示了最大堆和最小堆。


最大堆和最小堆

算法的图解

树型的堆化

从一个完整的二叉树开始，我们可以通过在堆的所有非叶元素上运行一个名为 heapify 的函数将其修改为一个最大堆。由于 heapify 使用递归，因此可能难以掌握。因此，让我们首先考虑如何用三个元素堆成一棵树。

heapify(array)
    Root = array[0]
    Largest = largest( array[0] , array [2*0 + 1]. array[2*0+2])
    if(Root != Largest)
          Swap(Root, Largest)


Heapify 基本案例

上面的例子展示了两种情况——一种是根是最大的元素，我们不需要做任何事情。另一个是根有一个更大的元素作为子元素，我们需要交换以保持最大堆属性。如果您以前使用过递归算法，您可能已经确定这必须是基本情况。现在让我们考虑另一种场景，其中存在多个级别。


当其子树已经是最大堆时如何堆化根元素

顶部元素不是最大堆，但所有子树都是最大堆。为了保持整个树的最大堆属性，我们必须不断向下推 2 直到它到达正确的位置。


当其子树为最大堆时如何堆化根元素

因此，为了在两个子树都是最大堆的树中维护最大堆属性，我们需要对根元素重复运行 heapify 直到它大于其子节点或它成为叶节点。我们可以将这两种条件组合在一个 heapify 函数中，如下所示：

void heapify(int arr[], int n, int i) {
  // Find largest among root, left child and right child
  int largest = i;
  int left = 2 * i + 1;
  int right = 2 * i + 2;

  if (left < n && arr[left] > arr[largest])
    largest = left;

  if (right < n && arr[right] > arr[largest])
    largest = right;

    // Swap and continue heapifying if root is not largest
    if (largest != i) {
      swap(&arr[i], &arr[largest]);
      heapify(arr, n, largest);
  }
}

此函数适用于基本情况和任何大小的树。因此，只要子树是最大堆，我们就可以将根元素移动到正确的位置，以保持任何树大小的最大堆状态。

构建最大堆

为了从任何树构建最大堆，我们可以从底向上开始堆化每个子树，并在将函数应用于包括根元素在内的所有元素后以最大堆结束。在完整树的情况下，非叶节点的第一个索引由 n/2 - 1 给出。之后的所有其他节点都是叶节点，因此不需要堆化。所以，我们可以建立一个最大堆：

// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
    heapify(arr, n, i);


创建数组并计算 i


为堆排序构建最大堆的步骤


为堆排序构建最大堆的步骤


为堆排序构建最大堆的步骤

如上图所示，我们从堆放最低的最小树开始，逐渐向上移动，直到到达根元素。如果到这里你已经理解了一切，那么恭喜你，你正在掌握堆排序。

堆排序工作

由于树满足最大堆属性，那么最大的项存储在根节点。
Swap：移除根元素并放在数组的末尾（第n个位置）将树（堆）的最后一项放在空的地方。
Remove：将堆的大小减少 1。
Heapify：再次堆化根元素，以便我们在根处拥有最大元素。
重复这个过程，直到列表的所有项目都被排序。


交换、移除和堆化

下面的代码显示了操作：

// Heap sort
for (int i = n - 1; i >= 0; i--) {
    swap(&arr[0], &arr[i]);

    // Heapify root element to get highest element at root again
    heapify(arr, i, 0);
}

算法的实现

// Heap Sort in Java

  public class HeapSort {

    public void sort(int arr[]) {
      int n = arr.length;

      // Build max heap
      for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
      }

      // Heap sort
      for (int i = n - 1; i >= 0; i--) {
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;

        // Heapify root element
        heapify(arr, i, 0);
      }
    }

    void heapify(int arr[], int n, int i) {
      // Find largest among root, left child and right child
      int largest = i;
      int l = 2 * i + 1;
      int r = 2 * i + 2;

      if (l < n && arr[l] > arr[largest])
        largest = l;

      if (r < n && arr[r] > arr[largest])
        largest = r;

      // Swap and continue heapifying if root is not largest
      if (largest != i) {
        int swap = arr[i];
        arr[i] = arr[largest];
        arr[largest] = swap;

        heapify(arr, n, largest);
      }
    }

    // Function to print an array
    static void printArray(int arr[]) {
      int n = arr.length;
      for (int i = 0; i < n; ++i)
        System.out.print(arr[i] + " ");
      System.out.println();
    }

    // Driver code
    public static void main(String args[]) {
      int arr[] = { 1, 12, 9, 5, 6, 10 };

      HeapSort hs = new HeapSort();
      hs.sort(arr);

      System.out.println("Sorted array is");
      printArray(arr);
    }
  }

算法复杂度

时间复杂度
最好的	O(nlog n)
最差	O(nlog n)
平均数	O(nlog n)
空间复杂度	O(1)
稳定性	不稳定

对于所有情况（最佳情况、平均情况和最坏情况），堆排序的时间复杂度都为 O(nlog n)。

让我们了解原因。包含 n 个元素的完全二叉树的高度为log n。

正如我们之前看到的，要完全堆化一个其子树已经是最大堆的元素，我们需要不断将元素与其左右子元素进行比较，并将其向下推，直到它到达两个子元素都小于它的点。在最坏的情况下，我们需要将元素从根节点移动到叶节点，进行多次log(n)比较和交换。

在 build_max_heap 阶段，我们对n/2元素执行此操作，因此 build_heap 步骤的最坏情况复杂度为 n/2*log n ~ nlog n。

在排序步骤中，我们将根元素与最后一个元素交换并堆化根元素。对于每个元素，这又花费了log n最糟糕的时间，因为我们可能必须将元素从根一直带到叶。既然我们重复这个n次， heap_sort 步骤也是nlog n.

另外由于build_max_heap和heap_sort这两个步骤是一个接一个执行的，所以算法复杂度没有成倍增加，保持nlog n的顺序。

它还以 O(1) 空间复杂度执行排序。与快速排序相比，它具有更好的最坏情况（ O(nlog n) ）。在最坏的情况下，快速排序的复杂度为 O(n^2)。但在其他情况下，快速排序很快。Introsort 是堆排序的替代方案，它结合了快速排序和堆排序，保留了两者的优点：最坏情况下的堆排序速度和快速排序的平均速度。

算法的应用

与安全性相关的系统和 Linux 内核等嵌入式系统使用堆排序，因为O(n log n)的Heapsort 的运行时间有O(1)的上限，并且其辅助存储有恒定上限。

尽管堆排序O(n log n)即使在最坏的情况下也具有时间复杂度，但它没有更多的应用程序（与快速排序、合并排序等其他排序算法相比）。但是，如果我们想从项目列表中提取最小（或最大）的项目，而无需将剩余元素保持在排序顺序中的开销，则可以有效地使用其底层数据结构堆。例如优先队列。

相似的算法

快速排序
归并排序

数据结构与算法

堆排序（Heap Sort）