堆排序

1. 堆排序算法
2. 堆排序示例
3. 堆排序算法的实现
4. 堆排序算法的复杂度

堆排序是一种基于比较的排序算法。它的名字来源于算法中使用的堆数据结构。堆是一种基于二叉树的特殊数据结构。它具有以下两个特性。

• 它是一棵完整的二叉树，除了最后一个层外，所有层都被填满。最后一层可能会被部分填满，但所有的节点都尽可能的向左。
• 所有的父节点都比它们的两个子节点小/大。如果它们较小，堆称为最小堆，如果较大，则堆称为最大堆。对于给定的索引 i，父节点由 (i-1)/2 给出，左子节点由 (2*i+1) 给出，右子节点由 (2*i+2) 给出。

堆排序的工作方式与选择排序很相似。它使用最大堆从数组中选择最大的元素，并将其放在数组后面的位置。它利用一个叫做 heapify() 的过程来建立堆。

堆排序算法

假设我们有一个包含 n 元素的未排序数组 A[]。

HeapSort()

Heapify()

堆排序示例

假设我们有数组。(5, 3, 4, 2, 1, 6). 我们将使用堆排序算法对其进行排序。

建立堆后，我们得到的数组为：(6 3 5 2 1 4)。(6 3 5 2 1 4)。

• 第一次迭代

• 第二次迭代

• 第三次迭代

• 第四次迭代

• 第五次迭代

• 第六次迭代

我们得到的排序数组为 ：(1,2,3,4,5,6)

堆排序算法的实现

#include <bits/stdc++.h>
using namespace std;

void heapify(int arr[], int n, int i) {
  int parent = i;
  int leftChild = 2 * i + 1;
  int rightChild = 2 * i + 2;

  if (leftChild < n && arr[leftChild] > arr[parent]) parent = leftChild;

  if (rightChild < n && arr[rightChild] > arr[parent]) parent = rightChild;

  if (parent != i) {
    swap(arr[i], arr[parent]);
    heapify(arr, n, parent);
  }
}

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

int main() {
  int n = 6;
  int arr[6] = {5, 3, 4, 2, 1, 6};
  cout << "Input array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  heapSort(arr, n);  // Sort elements in ascending order
  cout << "Output array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

堆排序算法的复杂度

时间复杂度

• 平均情况

具有 n 元素的完整二叉树的高度为最大 logn。因此，当一个元素从根到叶移动时，heapify() 函数可以有最大的 logn 比较。构建堆函数对 n/2 元素进行调用，使得第一阶段的总时间复杂度 n/2*logn 或 T(n)=nlogn。

HeapSort() 对每个元素都取 logn 最差时间，n 元素使其时间复杂度也为 nlogn。将建立堆和堆排序的时间复杂度相加，得到的复杂度为 nlogn。因此，总的时间复杂度是 [Big Theta]：O(nlogn)。

• 最坏情况

最坏情况下的时间复杂度为 [Big O]：O(nlogn)。

• 最佳情况

最佳情况下的时间复杂度是 [Big Omega]：O(nlogn)。它与最坏情况下的时间复杂度相同。

空间复杂度

堆排序算法的空间复杂度为 O(n)，因为除了临时变量外，不需要额外的内存。