排序算法丨堆排序

前言

堆排序(HeapSort),是指利用 堆 这种数据结构所设计的一种排序算法。它是 J.W.J.Williams 在 1964 年发明的。这也是堆诞生的时候,Williams 将其本身作为一个有用的数据结构提出。同年,Robert W.Floyd 发表了一个改进的版本,可以对数组进行就地排序,继续他早期对 treesort 算法的研究。

堆的定义

根据中文维基百科的定义,堆是一种特别的二叉树,满足以下条件的二叉树,可以称之为堆:

  1. 完全二叉树;
  2. 每一个节点的值都必须 大于等于或者小于等于 其孩子节点的值。

堆具有以下的特点:

  1. 可以在 O(logN) 的时间复杂度内向堆中插入元素;
  2. 可以在 O(logN) 的时间复杂度内向堆中删除元素;
  3. 可以在 O(1) 的时间复杂度内获取堆中的最大值或最小值。

堆的分类

堆有两种类型:最大堆(大顶堆)和最小堆(小顶堆)。

最大堆:堆中每一个节点的值 都大于等于 其孩子节点的值。所以最大堆的特性是 堆顶元素(根节点)是堆中的最大值。
最小堆:堆中每一个节点的值 都小于等于 其孩子节点的值。所以最小堆的特性是 堆顶元素(根节点)是堆中的最小值。


最大堆
最小堆

排序思路

大顶堆在堆排序算法中用于升序排列,而小顶堆相反,用于降序排列。

以大顶堆为例,堆排序过程如下:

  1. 创建堆(buildMaxHeap):用数列构建出一个大顶堆,取出堆顶的数字;
  2. 调整堆(maxHeapify):调整剩余的数字,构建出新的大顶堆,再次取出堆顶的数字;
  3. 堆排序(heapSort):循环往复,完成整个排序。

代码实现

public static void heapSort(int[] arr) {
    // 构建初始大顶堆
    buildMaxHeap(arr);
    for (int i = arr.length - 1; i > 0; i--) {
        // 将最大值放到数组最后
        exchange(arr, 0, i);
        // 调整剩余数组,使其满足大顶堆
        maxHeapify(arr, 0, i);
    }
}

// 构建初始大顶堆
public static void buildMaxHeap(int[] arr) {
    // 从最后一个非叶子结点开始调整大顶堆,最后一个非叶子结点的下标就是 arr.length / 2-1
    for (int i = arr.length / 2 - 1; i >= 0; i--) {
        maxHeapify(arr, i, arr.length);
    }
}

// 调整大顶堆,第三个参数表示剩余未排序的数字的数量,也就是剩余堆的大小
private static void maxHeapify(int[] arr, int i, int heapSize) {
    // 左子结点下标
    int l = 2 * i + 1;
    // 右子结点下标
    int r = l + 1;
    // 记录根结点、左子树结点、右子树结点三者中的最大值下标
    int largest = i;
    // 与左子树结点比较
    if (l < heapSize && arr[l] > arr[largest]) {
        largest = l;
    }
    // 与右子树结点比较
    if (r < heapSize && arr[r] > arr[largest]) {
        largest = r;
    }
    if (largest != i) {
        // 将最大值交换为根结点
        exchange(arr, i, largest);
        // 再次调整交换数字后的大顶堆
        maxHeapify(arr, largest, heapSize);
    }
}
// 交换元素
private static void exchange(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

动画演示

演示动画来源于visualgo


堆排序

复杂度分析

堆排序分为两个阶段:初始化建堆(buildMaxHeap)和重建堆(maxHeapify)。所以时间复杂度要从这两个方面分析。

根据数学运算可以推导出初始化建堆的时间复杂度为 O(n),重建堆的时间复杂度为 O(nlogn),故堆排序总的时间复杂度为 O(nlogn)。堆排序的空间复杂度为 O(1),只需要常数级的临时变量。

堆排序是一个优秀的排序算法,但是在实际应用中,快速排序的性能一般会优于堆排序,而且堆排序是不稳定的。

参考

菜鸟教程
程序员小灰
LeetCode
百度百科

打赏
评论区
头像
文章目录