堆排序

Harshit Jindal 2023年1月30日 2021年2月7日
  1. 堆排序算法
  2. 堆排序示例
  3. 堆排序算法的实现
  4. 堆排序算法的复杂度
堆排序

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

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

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

堆

堆排序算法

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

HeapSort()

  • 用数组 A 中的元素建立一个最大堆。
  • 对于从 A 中最后一个元素开始的每一个元素,执行以下操作。
  • 根元素 A[0] 将包含最大元素,将其与这个元素交换。
  • 将堆的大小减少一个,并 Heapify() 去掉最后一个元素后的最大堆。

Heapify()

  • 用当前元素的索引初始化 parent 索引。
  • 计算 leftChild2*i+1rightChild2*i+2
  • 如果 leftChild 处的元素大于 parent 索引处的值,则将 parent 索引设置为 leftChild
  • 如果 rightChild 处的元素大于 parent 索引处的值,则设置 parent 索引为 rightChild
  • 如果在上两步中,parent 索引的值发生了变化,那么将 parent 与当前元素交换,并递归 heapify parent 索引子树。否则,堆属性已经满足。

堆排序示例

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

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

  • 第一次迭代
Swap(A[5],A[0]) 4 3 5 2 1 6
Heapify() 5 3 4 2 1 6
  • 第二次迭代
Swap(A[4],A[0]) 1 3 4 2 5 6
Heapify() 4 3 1 2 5 6
  • 第三次迭代
Swap(A[3],A[0]) 2 3 1 4 5 6
Heapify() 3 2 1 4 5 6
  • 第四次迭代
Swap(A[2],A[0]) 1 2 3 4 5 6
Heapify() 2 1 3 4 5 6
  • 第五次迭代
Swap(A[1],A[0]) 1 2 3 4 5 6
Heapify() 1 2 3 4 5 6
  • 第六次迭代
Swap(A[0],A[0]) 1 2 3 4 5 6
Heapify() 1 2 3 4 5 6

我们得到的排序数组为 :(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*lognT(n)=nlogn

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

  • 最坏情况

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

  • 最佳情况

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

空间复杂度

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

Harshit Jindal avatar Harshit Jindal avatar

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.

LinkedIn

相关文章 - Sort Algorithm