DomBro Studio

堆排序-HeapSort

2017/12/04

堆排序-HeapSort

what

首先我们来了解一些枯燥概念。这往往是必须的(TT)。

堆 heap

  • 概念&公式

要了解堆排序,首先就要知道什么是堆!堆是顺序存储的完全二叉树(反正百度是这么说的)~ 翻译过来意思也就是堆实际就是逻辑上的完全二叉树,堆又分为 大根堆 和 小根堆 ,这个中文翻译很前卫… 分别有以下的特点

大根堆:每个节点的关键字(存储元素)都不小于其孩子节点的关键字,写成公式长这样

1
Ri >= R2i+1 且 Ri >= R2i+2 (i = 0,1,2...n)

小根堆:每个节点的关键字(存储元素)都不大于其孩子节点的关键字

1
Ri <= R2i+1 且 Ri <= R2i+2 (i = 0,1,2...n)

公式中的 i 就是顺序存储结构中的位置,可以把它理解为数组中的索引

  • 理解&总结

你可能还是有点乱,简单一句话,堆就是把一个数组按照每个元素的索引,变成一颗逻辑上的完全二叉树,例如一个元素在数组中的索引是 i ,该元素的左孩子在数组中的索引就是 2i+1,右孩子在数组中的索引就是 2i+2,父节点的索引就是 (i-1)/2,而这颗完全二叉树的每个节点元素与其子节点元素之间还要满足一定的大小关系

如图,是一个整型无序数组变为大根堆后的逻辑形态,每个节点元素都比其子节点大。

how

“堆排序” 这三个字你应该意识到,排序时一定会用到上面的堆,具体来说是大根堆。大根堆要如何实现排序?

堆排序 heap-sort

  • 大根堆的特点

你可能没注意到大根堆的一大特点:根节点是最大的! 也就是 索引为0 的元素是最大的。

  • 思路

根据大根堆特点,可以总结一下思路。首先我们将一个数组 arrary[0…n] 调整为大根堆后,在交换 array[0] 和 array[n]。然后调整 array[0…n-1] 为大根堆,在交换 array[0] 和 array[n-1],反复重复直到交换了 array[0] 和 array[1] 结束。

  • 思路归纳

根据上面的思路,可以归纳为两个操作:

1)根据初始数组构造初始堆(构建一个完全二叉树,保证所有父节点比孩子节点大,即大顶堆)。
2)每次交换第一个和最后一个元素,输出最后一个元素(此时为最大值),把剩下的元素构造为大顶堆,直到输出完数组中最后一个元素后,这个数组已经从小到大排列了。

注意,这里说的输出最后一个元素的意思是,在下一次调整数组为大顶堆不包括该元素!

初始化堆

我们建造大根堆的过程就是要保证每个节点的子节点都比该节点小的过程,若节点的一个子节点比该节点大则节点与该节点交换,若两个子节点均比该节点大,则交换更大的那个节点

  • 错误思路

初始化堆这里我踩了一点坑,所以拿出来说一说。一开始我想从根节点(索引为0)开始递增构建大根堆

如图,从根节点开始循环递增会出现最大的元素无法到到达根节点的尴尬局面。这肯定不是一个大根堆。

  • 正确思路

从中间的节点(索引n/2)开始递减构建大根堆,可以有效的解决上面的问题

如图在从中间(索引)遍历完每个节点后均保证了其子节点元素都比该元素小,构建大顶堆成功。

交换元素与调整

按照思路归纳中的步骤,初始化大根堆后,会交换根节点与最后一个元素,输出最后一个元素,可这时剩下元素组成的二叉树可能就不是大根堆了,所以还要将剩余元素变为大根堆,过程如下:

其实每次对剩余元素大根堆化的过程,与初始化大根堆是一样的,只不过传入的数组不包括上次交换的最后一个元素而已。到此,整个堆排序的过程也就介绍完了。

Java代码

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
/**
* 使用变治法的堆排序
*
* 分两步走:
* 第一步:将一个数组变为一个大根堆
* 第二步: 将该大根堆的根节点与最后一个元素进行交换,再将最后最后一个元素输出(此时最后一个元素是最大的元素)
*/
public class SeparateAndConquer {

/**
* 获取一个节点的左孩子在数组中位置
* @param parent 该左孩子
* @return
*/
private static int getLeftChild(int parent){
return 2*parent+1;
}

/**
*
* @param array 目标数组
* @param parent 节点在数组中的位置
* @param length 数组规模
*/
public static <AnyType extends Comparable<? super AnyType>> void buildHeap(AnyType[] array, int parent, int length){

//保存当前父节点
AnyType temp = array[parent];
//先获得左孩子位置
int child = getLeftChild(parent);

while (child < length){
//如果存在右孩子,并且右孩子值大于左孩子值,则选取右孩子节点
if (child + 1 < length && array[child].compareTo(array[child+1]) < 0){
child++;
}

//如果父亲结点值大于孩子节点的值,则直接结束
if (temp.compareTo(array[child]) > 0){
break;
}else{
//否则选取孩子节点的值赋给父节点
array[parent] = array[child];
//选取孩子节点的左孩子节点,继续向下筛选
parent = child;
child = 2 * child + 1;
}
}

array[parent] = temp;
}


public static <AnyType extends Comparable<? super AnyType>> void heapSort(AnyType[] array){
//首先将数组初始化为堆
for (int i = array.length/2; i >= 0; i--){
buildHeap(array,i,array.length);
}

//从最后一个元素开始循环(进行n-1次循环),完成排序
for (int i = array.length - 1; i > 0; i--){
//将最后一个元素与第一个元素交换
AnyType temp = array[i];
array[i] = array[0];
array[0] = temp;
//每次交换后,还要剩下的将最小的元素放回到最后一个位置,最大的元素放回到第一个位置
buildHeap(array,0,i);
System.out.format("第 %d 趟: \t", array.length - i);
printArray(array);
}
}

public static <AnyType extends Comparable<? super AnyType>> void printArray(AnyType[] array){
for (int i = 0; i < array.length;i++){
System.out.print(array[i]+" ");
}
System.out.println();
}

public static void main(String[] args) {

Integer[] array = {3,5,4,36,21};
System.out.println("使用堆排序前");
SeparateAndConquer.printArray(array);
SeparateAndConquer.heapSort(array);
System.out.println("使用堆排序后");
SeparateAndConquer.printArray(array);

}

}

运行结果

1
2
3
4
5
6
7
8
使用堆排序前
3 5 4 36 21
第 1 趟: 21 5 4 3 36
第 2 趟: 5 3 4 21 36
第 3 趟: 4 3 5 21 36
第 4 趟: 3 4 5 21 36
使用堆排序后
3 4 5 21 36

about

说完了怎么实现,再来分析一下堆排序算法

时间复杂度

经验表明,堆排序是个十分稳定的算法。堆排序给出了迄今为止最佳的大O运行时间。在第一步初始化堆阶段时间复杂度为 O(N),第二步在执行 N 次交换并调整大根堆所用时间复杂度为 O(NlogN),综合下来时间复杂度为 O(N)。

算法稳定性

堆排序是一种不稳定的排序方法。
因为在堆的调整过程中,关键字进行比较和交换所走的是该结点到叶子结点的一条路径,因此对于相同的关键字就可能出现排在后面的关键字被交换到前面来的情况。

CATALOG
  1. 1. 堆排序-HeapSort
    1. 1.1. what
      1. 1.1.1. 堆 heap
    2. 1.2. how
      1. 1.2.1. 堆排序 heap-sort
      2. 1.2.2. 初始化堆
      3. 1.2.3. 交换元素与调整
      4. 1.2.4. Java代码
      5. 1.2.5. 运行结果
    3. 1.3. about
      1. 1.3.1. 时间复杂度
      2. 1.3.2. 算法稳定性