堆排序算法

提示

1. 堆排序概念：堆排序是一种基于堆数据结构的有效排序算法，通过将数组元素视为特殊类型的完全二叉树来工作。
2. 实现过程：算法首先将数组转化为最大堆，然后不断从堆顶取出最大元素，调整堆结构，直至完成排序。
3. 时间和空间复杂度：堆排序在最佳、平均和最坏情况下的时间复杂度均为O(nlog n)，空间复杂度为O(1)。

堆排序是计算机编程中常用且高效的排序算法。学习如何编写堆排序算法需要了解两种数据结构 - 数组和树。

要排序的初始数字集合存储在数组中，例如[10, 3, 76, 34, 23, 32]，在排序后，我们得到一个排序好的数组[3, 10, 23, 32, 34, 76]。

堆排序通过将数组元素视为一种特殊类型的完全二叉树来工作，该树称为堆。

注意：作为先决条件，您必须了解完全二叉树和堆数据结构。

数组索引与树元素之间的关系

完全二叉树具有一个有趣的属性，我们可以使用它来查找任何节点的子节点和父节点。

如果数组中任何元素的索引是i，则索引为2i+1的元素将成为左子元素，索引为2i+2的元素将成为右子元素。此外，索引i处元素的父元素由(i-1)/2的下界给出。

让我们来测试一下，

1的左子节点（索引0）
= 索引1的元素
= 12


1的右子节点
= 索引2的元素
= 9

同样，
12的左子节点（索引1）
= 索引3的元素
= 5

12的右子节点
= 索引4的元素
= 6

让我们也确认规则是否适用于查找任何节点的父节点

9的父节点（位置2）
= （2-1）/2
= ½
= 0.5
~ 0索引
= 1

12的父节点（位置1）
= （1-1）/2
= 0索引
= 1

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

什么是堆数据结构？

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

• 它是完全二叉树。
• 树中的所有节点都遵循以下属性，即它们大于其子节点，即最大元素位于根部，其子节点都小于根节点，依此类推。这样的堆称为最大堆。如果相反，所有节点都小于其子节点，则称为最小堆。

下面的示例图显示了最大堆和最小堆。

要了解更多信息，请访问堆数据结构。

如何“堆化”一棵树

从一个完全二叉树开始，我们可以通过在堆的所有非叶元素上运行一个名为“堆化（heapify）”的函数来修改它，使其成为一个最大堆。

由于堆化使用了递归，它可能很难理解。因此，让我们首先考虑如何对具有三个元素的树进行堆化。

堆化（array）
    根节点 = array[0]
    最大值 = 最大值( array[0] , array [2*0 + 1]. array[2*0+2])
    if(根节点 != 最大值)
          交换(根节点, 最大值)

上面的示例显示了两种情况 - 一种情况下，根是最大的元素，我们不需要做任何事情。另一种情况下，根有一个更大的元素作为子节点，我们需要交换以保持最大堆属性。

如果您以前使用过递归算法，您可能已经确定这必须是基本情况。

现在让我们考虑另一种情况，其中有多个级别。

顶部元素不是最大堆，但所有子树都是最大堆。

为了在整个树中保持最大堆属性，我们必须将2向下推，直到它达到正确的位置。

因此，在维护树中的最大堆属性时，我们需要反复在根元素上运行堆化，直到它大于其子节点或成为叶节点。

我们可以将这两个条件合并到一个堆化函数中，如下所示：

void heapify(int arr[], int n, int i) {
  // 找到根、左子节点和右子节点中的最大值
  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;

    // 如果根不是最大的，则交换并继续堆化
    if (largest != i) {
      swap(&arr[i], &arr[largest]);
      heapify(arr, n, largest);
  }
}

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

建立最大堆

要从任何树构建一个最大堆，我们可以从底部向上堆化每个子树，并在应用到所有元素（包括根元素）后得到一个最大堆。

在完全树的情况下，非叶节点的第一个索引由n/2 - 1给出。之后的所有节点都是叶节点，因此不需要进行堆化。

因此，我们可以构建最大堆如下：

    // 构建堆（重新排列数组）
    for (int i = n / 2 - 1; i >= 0; i--)
      heapify(arr, n, i);

如上图所示，我们从对最小的树进行堆化开始，并逐渐向上移动，直到达到根元素。

如果你已经理解了到目前为止的所有内容，恭喜你，你正朝着掌握堆排序的方向迈进。

堆排序的工作原理

1. 由于树满足最大堆属性，因此最大的项存储在根节点中。
2. 交换： 移除根元素并放置在数组的末尾（第n个位置）。将树（堆）的最后一个项放到空出的位置上。
3. 移除： 减小堆的大小1。
4. 堆化： 再次堆化根元素，以便我们在根上有最高的元素。
5. 重复此过程，直到对列表中的所有项进行排序。

下面的代码显示了这个操作。

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

      // 再次堆化根元素以获得最高的元素
      heapify(arr, i, 0);
    }

Python、Java 和 C/C++ 中的堆排序代码

Python Java C C++

# Python 中的堆排序

def heapify(arr, n, i):
    # 找出根和子节点中最大的一个
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2

    if l < n and arr[i] < arr[l]:
        largest = l

    if r < n and arr[largest] < arr[r]:
        largest = r

    # 如果根不是最大的，则与最大的交换并继续堆化
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heapSort(arr):
    n = len(arr)

    # 构建最大堆
    for i in range(n//2, -1, -1):
        heapify(arr, n, i)

    for i in range(n-1, 0, -1):
        # 交换
        arr[i], arr[0] = arr[0], arr[i]

        # 堆化根元素
        heapify(arr, i, 0)

arr = [1, 12, 9, 5, 6, 10]
heapSort(arr)
n = len(arr)
print("排序后的数组为")
for i in range(n):
    print("%d " % arr[i], end='')

// 在 Java 中实现堆排序

public class HeapSort {

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

    // 构建最大堆
    for (int i = n / 2 - 1; i >= 0; i--) {
      heapify(arr, n, i);
    }

    // 堆排序
    for (int i = n - 1; i >= 0; i--) {
      int temp = arr[0];
      arr[0] = arr[i];
      arr[i] = temp;

      // 对根元素进行堆化
      heapify(arr, i, 0);
    }
  }

  void heapify(int arr[], int n, int i) {
    // 在根节点、左子节点和右子节点中找到最大的
    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;

    // 如果根不是最大的，则交换并继续堆化
    if (largest != i) {
      int swap = arr[i];
      arr[i] = arr[largest];
      arr[largest] = swap;

      heapify(arr, n, largest);
    }
  }

  // 打印数组的函数
  static void printArray(int arr[]) {
    int n = arr.length;
    for (int i = 0; i < n; ++i)
      System.out.print(arr[i] + " ");
    System.out.println();
  }

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

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

    System.out.println("排序后的数组为");
    printArray(arr);
  }
}

// 在 C 中实现堆排序

#include <stdio.h>

// 交换两个元素位置的函数
void swap(int *a, int *b) {
  int temp = *a;
  *a = *b;
  *b = temp;
}

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

  // Main function to do heap sort
  void heapSort(int arr[], int n) {
    // 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--) {
      swap(&arr[0], &arr[i]);

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

  // Print an array
  void printArray(int arr[], int n) {
    for (int i = 0; i < n; ++i)
      printf("%d ", arr[i]);
    printf("\n");
  }

  // Driver code
  int main() {
    int arr[] = {1, 12, 9, 5, 6, 10};
    int n = sizeof(arr) / sizeof(arr[0]);

    heapSort(arr, n);

    printf("Sorted array is \n");
    printArray(arr, n);
  }

#include <iostream>
using namespace std;

void heapify(int arr[], int n, int i) {
    // 在根、左子节点和右子节点中找到最大值
    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;

    // 如果根不是最大的，则交换并继续堆化
    if (largest != i) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

void heapSort(int arr[], int n) {
    // 构建最大堆
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    // 堆排序
    for (int i = n - 1; i >= 0; i--) {
        swap(arr[0], arr[i]);

        // 再次堆化根元素以获得最高的元素
        heapify(arr, i, 0);
    }
}

  // Print an array
  void printArray(int arr[], int n) {
    for (int i = 0; i < n; ++i)
      cout << arr[i] << " ";
    cout << "\n";
  }

  // Driver code
  int main() {
    int arr[] = {1, 12, 9, 5, 6, 10};
    int n = sizeof(arr) / sizeof(arr[0]);

    heapSort(arr, n);

    cout << "排序后的数组为：" << endl;
    printArray(arr, n);
    return 0;
}

堆排序复杂性

时间复杂性
最佳情况	O(nlog n)
最坏情况	O(nlog n)
平均情况	O(nlog n)
空间复杂性	O(1)
---	---
稳定性	否
---	---

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

让我们理解其中的原因。包含n个元素的完全二叉树的高度是log n。

正如我们之前看到的，要完全将一个已经是最大堆的元素堆化，我们需要不断将该元素与其左右子节点进行比较，并将其向下推，直到达到一个状态，其中其两个子节点都小于它。

在最坏情况下，我们需要将一个元素从根节点移动到叶节点，进行多次log(n)次比较和交换。

在构建最大堆的阶段，我们对n/2个元素执行此操作，因此构建堆的步骤的最坏情况复杂性为n/2 * log n ~ nlog n。

在排序步骤中，我们将根元素与最后一个元素交换，并对根元素进行堆化。对于每个元素，这同样需要最坏情况下的log n时间，因为我们可能需要将元素从根节点一直移动到叶节点。由于我们重复这个过程n次，堆排序步骤也是nlog n。

此外，由于build_max_heap和heap_sort步骤是依次执行的，算法复杂性没有相乘，保持在nlog n的数量级。

另外，堆排序在O(1)的空间复杂度下执行排序。与快速排序相比，它具有更好的最坏情况时间复杂度（O(nlog n)）。快速排序在最坏情况下的复杂度为O(n^2)。但在其他情况下，快速排序更快。Introsort是堆排序的替代方法，它结合了快速排序和堆排序的优点，既具有堆排序的最坏情况速度，又具有快速排序的平均速度。

堆排序应用

关注安全性的系统和嵌入式系统，例如Linux内核，使用堆排序，因为堆排序的运行时间上界为O(n log n)，辅助存储的上界为O(1)。

尽管堆排序即使在最坏情况下也具有O(n log n)的时间复杂度，但与其他排序算法（如快速排序、归并排序）相比，它的应用不如其他排序算法多。然而，其底层数据结构堆可在不保持其余项目按排序顺序排列的情况下，高效地用于从项目列表中提取最小（或最大）的情况。例如，优先队列。

相似的排序算法

1. 快速排序
2. 归并排序