堆排序及其优化

堆排序基本理解

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

排序过程图示


首先,将元素进行重排,以匹配堆的条件。图中排序过程之前简单的绘出了堆树的结构

复杂度分析

分类 排序算法
数据结构 数组
最坏时间复杂度$O(nlogn)$
最优时间复杂度 $O(nlogn)$
空间复杂度 O(n) total,O(1) auxiliary

普通实现代码

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
package Heap.HeapSort;

/**
* @ Description: 低效的堆排序
* @ Date: Created in 08:47 2018/7/31
* @ Author: Anthony_Duan
*/
public class HeapSort {

private HeapSort(){}

/**
* 将所有的元素依次添加到堆中, 在将所有元素从堆中依次取出来, 即完成了排序
* 无论是创建堆的过程, 还是从堆中依次取出元素的过程, 时间复杂度均为O(nlogn)
* 整个堆排序的整体时间复杂度为O(nlogn)
* @param arr
*/
public static void sort(Comparable[] arr) {
int n = arr.length;
MaxHeapWithHeapify<Comparable> maxHeapWithHeapify = new MaxHeapWithHeapify<Comparable>(n);

for (int i = 0; i < n; i++) {
maxHeapWithHeapify.insert(arr[i]);
}

for (int i = n-1; i >= 0; i--) {
arr[i] = maxHeapWithHeapify.extractMax();
}
}
public static void main(String[] args) {

int N = 1000000;
Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
SortTestHelper.testSort("Heap.HeapSort.HeapSort", arr);

return;
}

}

优化方法

在堆的构造方法中添加Heapify操作(将一个数组通过shiftDown高效的转化为堆)
MaxHeapWithHeapify类

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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
package Heap.HeapSort;

/**
* @ Description: 最大堆中添加Heapify操作
* @ Date: Created in 08:16 2018/7/31
* @ Author: Anthony_Duan
*/
// 在堆的有关操作中,需要比较堆中元素的大小,所以Item需要extends Comparable
public class MaxHeapWithHeapify<Item extends Comparable> {

protected Item[] data;
protected int count;
protected int capacity;

//构造函数,构造一个空堆,可容纳capacity个元素 多开辟1个空间是为了让索引从1开始便于计算
public MaxHeapWithHeapify(int capacity) {
data = (Item[]) new Comparable[capacity + 1];
count = 0;
this.capacity = capacity;
}


/**
* Heapify的实现 利用构造函数
* 该构造堆的过程,时间复杂度为O(n)
* @param arr
*/
public MaxHeapWithHeapify(Item arr[]) {
int n = arr.length;
data = (Item[]) new Comparable[n + 1];
capacity = n;
for (int i = 0; i < n; i++) {
data[i + 1] = arr[i];
}
count = n;
for (int i = count / 2; i >= 1; i--) {
shiftDown(i);
}
}


//返回堆中元素的个数
public int size() {
return count;
}

//返回堆是否为空
public boolean isEmpty() {
return count == 0;
}


//向最大堆中插入一个新的元素item
public void insert(Item item) {
assert count + 1 <= capacity;
data[count + 1] = item;
count++;
shiftUp(count);
}

//从最大堆中取出堆顶的元素,即堆中所存储的最大元素
public Item extractMax() {
assert count > 0;
Item ret = data[1];

swap(1, count);
count--;
shiftDown(1);
return ret;
}

//获取最大堆中的堆顶元素
public Item getMax() {
assert (count > 0);
return data[1];
}

//交换堆中索引为i何j的两个元素
private void swap(int i, int j) {
Item t = data[i];
data[i] = data[j];
data[j] = t;
}


/**
* 堆的核心辅助函数,上浮操作
* @param k
*/
private void shiftUp(int k) {
while (k > 1 && data[k / 2].compareTo(data[k]) < 0) {
swap(k, k / 2);
k /= 2;
}
}


/**
* 堆的核心辅助函数,下沉操作
* @param k
*/
private void shiftDown(int k) {
while (2 * k <= count) {
int j = 2 * k;
if (j + 1 <= count && data[j + 1].compareTo(data[j]) > 0) {
j++;
}
if (data[k].compareTo(data[j]) >= 0) {
break;
}
swap(k, j);
k = j;
}
}
// 测试 MaxHeapWithHeapify
public static void main(String[] args) {

MaxHeapWithHeapify<Integer> maxHeapWithHeapify = new MaxHeapWithHeapify<Integer>(100);
int N = 100; // 堆中元素个数
int M = 100; // 堆中元素取值范围[0, M)
for( int i = 0 ; i < N ; i ++ ) {
maxHeapWithHeapify.insert( new Integer((int)(Math.random() * M)) );
}

Integer[] arr = new Integer[N];
// 将maxheap中的数据逐渐使用extractMax取出来
// 取出来的顺序应该是按照从大到小的顺序取出来的
for( int i = 0 ; i < N ; i ++ ){
arr[i] = maxHeapWithHeapify.extractMax();
System.out.print(arr[i] + " ");
}
System.out.println();

// 确保arr数组是从大到小排列的
for( int i = 1 ; i < N ; i ++ ) {
assert arr[i-1] >= arr[i];
}
}
}

HeapSortWithHeapify类

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
package Heap.HeapSort;


/**
* @ Description:使用Heapify初始化输出的堆排序
* @ Date: Created in 08:55 2018/7/31
* @ Author: Anthony_Duan
*/
public class HeapSortWithHeapify {

private HeapSortWithHeapify(){}

/**
* 使用Heapify过程创建堆
* 此时,创建堆的过程时间复杂度为O(n),将所有元素一次从堆中取出来实践复杂度为O(nlogn)
* 堆排序的总体时间复杂度依然是O(nlogn), 但是比HeapSort性能更优, 因为创建堆的性能更优
* @param arr
*/
public static void sort(Comparable[] arr) {
int n = arr.length;
MaxHeapWithHeapify<Comparable> maxHeapWithHeapify = new MaxHeapWithHeapify<Comparable>(arr);

for (int i = n - 1; i >= 0; i--) {
arr[i] = maxHeapWithHeapify.extractMax();
}
}
public static void main(String[] args) {

int N = 1000000;
Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
SortTestHelper.testSort("Heap.HeapSort.HeapSortWithHeapify", arr);

return;
}
}

-------------End Of This ArticleThank You For Reading-------------