排序六 堆排序

堆的概念

在介绍堆排序之前,首先需要说明一下,堆是个什么玩意儿。

是一棵顺序存储完全二叉树

其中每个结点的关键字都不大于其孩子结点的关键字,这样的堆称为小根堆

其中每个结点的关键字都不小于其孩子结点的关键字,这样的堆称为大根堆

举例来说,对于n个元素的序列{R0, R1, ... , Rn}当且仅当满足下列关系之一时,称之为堆:

(1) Ri <= R2i+1 且 Ri <= R2i+2 (小根堆)

(2) Ri >= R2i+1 且 Ri >= R2i+2 (大根堆)

其中i=1,2,…,n/2向下取整; 

如上图所示,序列R{3, 8, 15, 31, 25}是一个典型的小根堆。

堆中有两个父结点,元素3和元素8。

元素3在数组中以R[0]表示,它的左孩子结点是R[1],右孩子结点是R[2]。

元素8在数组中以R[1]表示,它的左孩子结点是R[3],右孩子结点是R[4],它的父结点是R[0]。可以看出,它们满足以下规律

设当前元素在数组中以R[i]表示,那么,

(1) 它的左孩子结点是:R[2*i+1];

(2) 它的右孩子结点是:R[2*i+2];

(3) 它的父结点是:R[(i-1)/2];

(4) R[i] <= R[2*i+1] 且 R[i] <= R[2i+2]。

要点

首先,按堆的定义将数组R[0..n]调整为堆(这个过程称为创建初始堆),交换R[0]和R[n];

然后,将R[0..n-1]调整为堆,交换R[0]和R[n-1];

如此反复,直到交换了R[0]和R[1]为止。

以上思想可归纳为两个操作:

(1)根据初始数组去构造初始堆(构建一个完全二叉树,保证所有的父结点都比它的孩子结点数值大)。

(2)每次交换第一个和最后一个元素,输出最后一个元素(最大值),然后把剩下元素重新调整为大根堆。

当输出完最后一个元素后,这个数组已经是按照从小到大的顺序排列了。

先通过详细的实例图来看一下,如何构建初始堆。

设有一个无序序列 { 1, 3, 4, 5, 2, 6, 9, 7, 8, 0 }。

构造了初始堆后,我们来看一下完整的堆排序处理:

还是针对前面提到的无序序列 { 1, 3, 4, 5, 2, 6, 9, 7, 8, 0 } 来加以说明。

相信,通过以上两幅图,应该能很直观的演示堆排序的操作处理。

核心代码

public void HeapAdjust(int[] array, int parent, int length) {
 int temp = array[parent]; // temp保存当前父节点
  int child = 2 * parent + 1; // 先获得左孩子
  
 while (child < length) {
 // 如果有右孩子结点,并且右孩子结点的值大于左孩子结点,则选取右孩子结点
  if (child + 1 < length && array[child] < array[child + 1]) {
             child++;
         }
 
 // 如果父结点的值已经大于孩子结点的值,则直接结束
  if (temp >= array[child])
 break;
 
 // 把孩子结点的值赋给父结点
         array[parent] = array[child];
 
 // 选取孩子结点的左孩子结点,继续向下筛选
         parent = child;
         child = 2 * child + 1;
     }
 
     array[parent] = temp;
 }
 
 public void heapSort(int[] list) {
 // 循环建立初始堆
  for (int i = list.length / 2; i >= 0; i--) {
         HeapAdjust(list, i, list.length);
     }
 
 // 进行n-1次循环,完成排序
  for (int i = list.length - 1; i > 0; i--) {
 // 最后一个元素和第一元素进行交换
  int temp = list[i];
         list[i] = list[0];
         list[0] = temp;
 
 // 筛选 R[0] 结点,得到i-1个结点的堆
         HeapAdjust(list, 0, i);
         System.out.format("第 %d 趟: \t", list.length - i);
         printPart(list, 0, list.length - 1);
     }
 }

算法分析

堆排序算法的总体情况

排序类别

排序方法

时间复杂度

空间复杂度

稳定性

复杂性

平均情况

最坏情况

最好情况

选择排序

堆排序

O(nlog2n)

O(nlog2n)

O(nlog2n)

O(1)

不稳定

较复杂

时间复杂度

堆的存储表示是顺序的。因为堆所对应的二叉树为完全二叉树,而完全二叉树通常采用顺序存储方式。

当想得到一个序列中第k个最小的元素之前的部分排序序列,最好采用堆排序。

因为堆排序的时间复杂度是O(n+klog2n),若k≤n/log2n,则可得到的时间复杂度为O(n)

算法稳定性

堆排序是一种不稳定的排序方法。

因为在堆的调整过程中,关键字进行比较和交换所走的是该结点到叶子结点的一条路径,

因此对于相同的关键字就可能出现排在后面的关键字被交换到前面来的情况。

完整参考代码

JAVA版本

代码实现

以下范例是对上文提到的无序序列 { 1, 3, 4, 5, 2, 6, 9, 7, 8, 0 } 进行排序。

public class HeapSort {
 
    public void HeapAdjust(int[] array, int parent, int length) {
        int temp = array[parent]; // temp保存当前父节点
        int child = 2 * parent + 1; // 先获得左孩子
 
        while (child < length) {
            // 如果有右孩子结点,并且右孩子结点的值大于左孩子结点,则选取右孩子结点
            if (child + 1 < length && array[child] < array[child + 1]) {
                child++;
            }
 
            // 如果父结点的值已经大于孩子结点的值,则直接结束
            if (temp >= array[child])
                break;
 
            // 把孩子结点的值赋给父结点
            array[parent] = array[child];
 
            // 选取孩子结点的左孩子结点,继续向下筛选
            parent = child;
            child = 2 * child + 1;
        }
 
        array[parent] = temp;
    }
 
    public void heapSort(int[] list) {
        // 循环建立初始堆
        for (int i = list.length / 2; i >= 0; i--) {
            HeapAdjust(list, i, list.length);
        }
 
        // 进行n-1次循环,完成排序
        for (int i = list.length - 1; i > 0; i--) {
            // 最后一个元素和第一元素进行交换
            int temp = list[i];
            list[i] = list[0];
            list[0] = temp;
 
            // 筛选 R[0] 结点,得到i-1个结点的堆
            HeapAdjust(list, 0, i);
            System.out.format("第 %d 趟: \t", list.length - i);
            printPart(list, 0, list.length - 1);
        }
    }
 
    // 打印序列
    public void printPart(int[] list, int begin, int end) {
        for (int i = 0; i < begin; i++) {
            System.out.print("\t");
        }
        for (int i = begin; i <= end; i++) {
            System.out.print(list[i] + "\t");
        }
        System.out.println();
    }
 
    public static void main(String[] args) {
        // 初始化一个序列
        int[] array = {
                1, 3, 4, 5, 2, 6, 9, 7, 8, 0
        };
 
        // 调用快速排序方法
        HeapSort heap = new HeapSort();
        System.out.print("排序前:\t");
        heap.printPart(array, 0, array.length - 1);
        heap.heapSort(array);
        System.out.print("排序后:\t");
        heap.printPart(array, 0, array.length - 1);
    }
}

运行结果

排序前:    1   3   4   5   2   6   9   7   8   0  
 第 1 趟:   8   7   6   5   2   1   4   3   0   9  
 第 2 趟:   7   5   6   3   2   1   4   0   8   9  
 第 3 趟:   6   5   4   3   2   1   0   7   8   9  
 第 4 趟:   5   3   4   0   2   1   6   7   8   9  
 第 5 趟:   4   3   1   0   2   5   6   7   8   9  
 第 6 趟:   3   2   1   0   4   5   6   7   8   9  
 第 7 趟:   2   0   1   3   4   5   6   7   8   9  
 第 8 趟:   1   0   2   3   4   5   6   7   8   9  
 第 9 趟:   0   1   2   3   4   5   6   7   8   9  
 排序后:    0   1   2   3   4   5   6   7   8   9  

参考资料

《数据结构习题与解析》(B级第3版)

相关阅读

欢迎阅读 程序员的内功——算法 系列

示例源码:https://github.com/dunwu/algorithm-notes

说明

感谢 @放学路上的小学生 的指正,他提到的第一种修改方法是有效的。本文已修改。

在我的 github 中,提供了单元测试来进行排序验证:

样本包含:数组个数为奇数、偶数的情况;元素重复或不重复的情况。且样本均为随机样本,实测有效。

https://github.com/dunwu/algorithm-notes/blob/master/codes/src/test/java/io/github/dunwu/algorithm/sort/SortStrategyTest.java

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Java爬坑系列

【Java入门提高篇】Day26 Java容器类详解(八)HashSet源码分析

  前面花了好几篇的篇幅把HashMap里里外外说了个遍,大家可能对于源码分析篇已经讳莫如深了。

1144
来自专栏用户画像

7.7.5 最佳归并树

文件经过置换-选择排序之后,得到的是长度不等的初始归并段。下面讨论如何组织初始归并段的归并顺序,使I/O访问次数最少。

801
来自专栏猿人谷

二叉搜索树的后序遍历序列

题目:输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true,否则返回false。 例如输入5、7、6、9、11、10、8,由于这一...

2087
来自专栏俞其荣的博客

HashMap内部原理解析HeaderHashMap 必知源码分析Java 1.8 中 HashMap 的不同Footer

28010
来自专栏开发之途

Java集合框架源码解析之HashSet

1264
来自专栏阿杜的世界

经典面试题之链表

911
来自专栏来自地球男人的部落格

[LeetCode] 78. Subsets

【原题】 Given a set of distinct integers, nums, return all possible subsets. Not...

2769
来自专栏计算机视觉与深度学习基础

Leetcode 209 Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minima...

20810
来自专栏cmazxiaoma的架构师之路

通过分析LinkedHashMap了解LRU

我们都知道LRU是最近最少使用,根据数据的历史访问记录来进行淘汰数据的。其核心思想是如果数据最近被访问过,那么将来访问的几率也更高。在这里提一下,Redis缓存...

1543
来自专栏来自地球男人的部落格

[LeetCode] 39.Combination Sum

【原题】 Given a set of candidate numbers (C) (without duplicates) and a target ...

2157

扫码关注云+社区

领取腾讯云代金券