排序六 堆排序

堆的概念

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

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

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

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

举例来说,对于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 条评论
登录 后参与评论

相关文章

来自专栏郭耀华‘s Blog

《剑指offer》全部题目-含Java实现

陆续刷了好久,算是刷完了《剑指offer》,以下全部AC代码,不一定性能最优,如有错误或更好解答,请留言区指出,大家共同交流,谢谢~ 1.二维数组中的查找 在...

6127
来自专栏null的专栏

剑指Offer——编程题的Java实现

声明:我写这个的意图是我在看书的过程中,就我掌握的内容做一个笔记,没有抄袭的意图。再次说明一下,我找工作的过程中并不顺利,没有像那些牛人们拿到一大把的Offer...

5863
来自专栏数据结构与算法

二叉树的遍历

解决二叉树的很多问题的方案都是基于对二叉树的遍历。遍历二叉树的前序,中序,后序三大方法算是计算机科班学生必写代码了。其递归遍历是人人都能信手拈来,可是在手生时写...

3344
来自专栏书山有路勤为径

逆序数(二叉查找树)

已知数组nums,求新数组count,count[i]代表了在nums[i]右侧且比nums[i]小的元素个数。 例如: nums = [5,2,6,1],...

593
来自专栏xcywt

《大话数据结构》 查找 以及一个简单的哈希表例子

第八章 查找 定义:查找就是根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素(或记录)。 8.2 查找概论 查找表(Search table):...

59512
来自专栏趣谈编程

可以管理时间的二叉堆

面试官:写一个堆排吧 我心想:堆排是什么鬼 理解堆排,首先要理解二叉堆。理解了二叉堆的“下沉”操作,基本上就可以理解堆排了。今天我们来看一看什么是堆,以及堆...

1866
来自专栏郭耀华‘s Blog

剑指offer 第十二天

58.对称的二叉树 请实现一个函数,用来判断一颗二叉树是不是对称的。注意,如果一个二叉树同此二叉树的镜像是同样的,定义其为对称的。 /* public clas...

2895
来自专栏机器学习与自然语言处理

04-树5. File Transfer--并查集

  对于一个集合常见的操作有:判断一个元素是否属于一个集合;合并两个集合等等。而并查集是处理一些不相交集合(Disjoint Sets)的合并及查询问题的有利工...

1785
来自专栏云霄雨霁

数据压缩----霍夫曼树和霍夫曼压缩

1670
来自专栏java一日一条

经典数据结构和算法回顾

最近想回过头来看看以前写的一些代码,可叹为何刚进大学的时候不知道要养成写博客的好习惯。现在好多东西都没有做记录,后面也没再遇到相同的问题,忘的都差不多了。只能勉...

471

扫码关注云+社区