算法渣-排序-堆排序

没有一身好内功,招式再多都是空;算法绝对是防身必备,面试时更是不可或缺;跟着算法渣一起从零学算法

定义

堆排序(英语:Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。

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

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

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

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

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

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

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

同时,我们对堆中的结点按层进行编号,将这种逻辑结构映射到数组中就是下面这个样子

完全二叉树

完全二叉树的定义是建立在满二叉树定义的基础上的,而满二叉树又是建立在二叉树的基础上的。

二叉树

二叉树是树的特殊一种,具有如下特点:

  1. 每个结点最多有两颗子树,结点的度最大为2。
  2. 左子树和右子树是有顺序的,次序不能颠倒。
  3. 即使某结点只有一个子树,也要区分左右子树。

满二叉树

所有的分支结点都存在左子树和右子树,并且所有的叶子结点都在同一层上,这样就是满二叉树。就是完美圆满的意思,关键在于树的平衡

根据满二叉树的定义,得到其特点为:

  1. 叶子只能出现在最下一层。
  2. 非叶子结点度一定是2.
  3. 在同样深度的二叉树中,满二叉树的结点个数最多,叶子树最多。

完全二叉树

对于一个树高为h的二叉树,如果其第0层至第h-1层的节点都满。如果最下面一层节点不满,则所有的节点在左边的连续排列,空位都在右边。这样的二叉树就是一棵完全二叉树

在上图中,树1,按层次编号5结点没有左子树,有右子树,10结点缺失。树2由于3结点没有字数,是的6,7位置空挡了。树3中结点5没有子树。

完全二叉树

上图就是一个完全二叉树

算法

利用堆顶记录的是最大(以大顶堆为例)关键字这一特性,每一轮取堆顶元素放入有序区,就类似选择排序每一轮选择一个最大值放入有序区,可以把堆排序看成是选择排序的改进。

  1. 将初始待排序关键字序列(R0,R1,R2….Rn)构建成大顶堆,此堆为初始的无序区;

  2. 将堆顶元素R[0]与最后一个元素R[n]交换,此时得到新的无序区(R0,R1,R2,……Rn-1)和新的有序区(Rn);

  3. 由于交换后新的堆顶R[0]可能违反堆的性质,因此需要对当前无序区(R0,R1,R2,……Rn-1)调整为新堆

不断重复此2、3步骤直到有序区的元素个数为n-1,则整个排序过程完成

演示

  1. 由一个无序序列建成一个堆
  2. 输出堆顶元素之后,调整剩余元素成为一个新的堆

1.构造堆

构造初始堆,将给定无序序列构造成一个大顶堆(一般升序采用大顶堆,降序采用小顶堆)

数组是一个无序结构

因为(n/2-1)~0的节点才有子节点,n=5,(n/2-1) = 1 即1 0节点才有子节点

所以将1 0节点从下到上,从右到左的与它自己的子节点比较并调整最终形成大顶堆

1. 节点1和它的子节点3 4的元素进行比较,最大者作为父节点

2. 将节点0和它的子节点1 2的元素进行比较,最大者为父节点

3. 交换导致了子根[4,5,6]结构混乱,继续调整,[4,5,6]中6最大,交换4和6

构造完成将一个无需序列构造成了一个大顶堆

2. 调整堆

将堆顶元素与末尾元素进行交换,使末尾元素最大。然后继续调整堆,再将堆顶元素与末尾元素交换,得到第二大元素。如此反复进行交换、重建、交换。

1. 将堆顶元素9和末尾元素4进行交换

2. 重新调整结构,使其继续满足堆定义

3. 再将堆顶元素8与末尾元素5进行交换,得到第二大元素8

4. 继续进行调整,交换,如此反复进行,最终使得整个序列有序

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
 /**
*
* a.将无需序列构建成一个堆,根据升序降序需求选择大顶堆或小顶堆;

 b.将堆顶元素与末尾元素交换,将最大元素"沉"到数组末端;

 c.重新调整结构,使其满足堆定义,然后继续交换堆顶元素与当前末尾元素,反复执行调整+交换步骤,直到整个序列有序。

* 整个排序过程,就是构造堆的过程
*
* 这儿写得利于理解一点,把最后一步改掉,循环从数组中把第一位取出来放到新数组,剩余的再去构造堆
* @param array
*/
static void heapSort(int []array) {
//原始数组
int [] oriental = Arrays.copyOf(array,array.length);
//最终排序好的数组
int [] result = new int[array.length];

int length = array.length;
for ( int i = 0;i< length;i++) {
//1.构造堆
buildHeap(array);
//构建完array[0]就是最大的元素,取出来放到排序好的数组
result[i] = array[0];
//[0]取走之后,一个新数组,再去构造堆
array = Arrays.copyOfRange(array, 1,length-i);
}
System.out.println("finish:"+ Arrays.toString(result));
}

/**
* 构造椎
* @param array
*/
static void buildHeap(int []array) {
//(n/2-1)~0的节点才有子节点
for (int i= array.length/2 -1 ;i>=0;i--) {
// System.out.println("i:"+i);
// System.out.println("start:"+ Arrays.toString(array));
int k = i;
for (int left = k * 2 + 1; left < array.length; left = k * 2 + 1) {
// System.out.println("build:"+ Arrays.toString(array));
int max = left;
int right = left + 1;
//有右节点
if (right < array.length) {
if (array[right] > array[left]) {
max = right;
}
}
//max是left子节点,那就交换左子节点与k
if (array[max] > array[k]) {
swap(array, max, k);
// 下面就是非常关键的一步了
// 如果子节点更换了,那么,以子节点为根的子树会不会受到影响呢?
// 所以,循环对子节点所在的树继续进行判断
k = left;
} else {
break;
}
}
}
//System.out.println(" end:"+ Arrays.toString(array));
}

详细代码:
https://github.com/zhuxingsheng/javastudy/tree/master/src/main/java/com/jack/algorithms/sort

复杂度

Best Average Worst Memory Stable
n log(n) n log(n) n log(n) 1 No

参考资料

图解排序算法(三)之堆排序

图解堆排序

朱兴生 wechat
最新文章尽在微信公众号『码农戏码』