堆排序算法实现，欢迎交流，指正错误。
1. 堆排序
堆排序（英语：Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
堆又分为大根堆和小根堆：
大根堆：根节点不小于左右子树中的所有节点，即根节点的值最大。左右子树也满足该性质。
小根堆：根节点不大于左右子树中的所有节点，即根节点的值最小。左右子树也满足该性质。
堆的逻辑结构是一颗完全二叉树，而物理结构（存储结构）是一个数组。
堆排序的基本思路：
- 将数组构建成一个大（小）根堆;
- 弹出堆的根节点；
- 调整使其依然是大（小）根堆；
- 重复2-3，直至所有元素都弹出。
若需要实现非递减排序，则应建立大根堆（因为每次弹出的都是根节点是放在未排序数组的最后）；
同理，若需要实现非递增排序，则应建立小根堆。
1.1. 复杂度分析
- 时间复杂度（平均）：O(nlogn)
- 时间复杂度（最坏）：O(nlogn)
- 时间复杂度（最好）：O(nlogn)
- 空间复杂度：O(1)
- 稳定性：不稳定
2. 非递减排序实现
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
|
/**
* 基于大根堆实现非递减排序
* @param arr 待排序数组
*/
public void bigHeapSort(int[] arr) {
if (null == arr || 1 >= arr.length) return;
// 边界值。 边界左边的是未排序部分，边界右边的是已排序部分。
int boundary = arr.length - 1;
buildBigHeap(arr); // 构建初始大根堆
swap(arr, 0, boundary); // 保存当前堆顶到末尾
while (--boundary >= 0) {
adjustBig(arr, 0, boundary); // 调整每个子堆为大根堆
swap(arr, 0, boundary); // 保存当前堆顶到末尾
}
}
/**
* 构建原始大根堆
*/
private void buildBigHeap(int[] arr) {
// 最后一个非叶子节点为 len / 2 - 1
int n = arr.length / 2 - 1; // 从最后一个非叶子节点开始
for (int i = n; i >= 0 ; i--) {
adjustBig(arr, i, arr.length - 1);
}
}
/**
* 调整子堆为大根堆
*/
private void adjustBig(int[] arr, int top, int boundary) {
exchangeBig(arr, top, 2 * top + 1, boundary);
exchangeBig(arr, top, 2 * top + 2, boundary);
}
/**
* 与子节点比较，并调整子堆为大根堆
*/
private void exchangeBig(int[] arr, int top, int sub, int boundary) {
if (sub > boundary) return;
if (arr[top] < arr[sub]) {
swap(arr, top, sub);
adjustBig(arr, sub, boundary);
}
}
/**
* 交换数组中的两个元素
* 注：此种方法有一个缺陷，i 不可与 j 相等
*/
private void swap(int[] arr, int i, int j) {
if (i == j) return;
arr[i] += arr[j];
arr[j] = arr[i] - arr[j];
arr[i] = arr[i] - arr[j];
}
|
3. 非递增排序实现
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
|
/**
* 基于小跟堆的非递增排序实现
* @param arr 待排序数组
*/
public void smallHeapSort(int[] arr){
if(arr == null || arr.length == 0) return;
// 边界值。 边界左边的是未排序部分，边界右边的是已排序部分。
int boundary = arr.length - 1;
buildSmallHeap(arr);// 构建小跟堆
swap(arr, 0, boundary);
while (--boundary >= 0){
adjustSmall(arr, 0, boundary);// 调整每个子堆为小根堆
swap(arr, 0 ,boundary);//保存当前堆顶到末尾
}
}
/**
* 构建原始小根堆
*/
private void buildSmallHeap(int[] arr) {
//从最后一个非叶子节点开始
int n = arr.length / 2 - 1;
for(int i = n; i >= 0; i--){
adjustSmall(arr, i, arr.length - 1);
}
}
/**
* 调整子堆为小根堆
*/
private void adjustSmall(int[] arr, int top, int boundary) {
exchangeSmall(arr, top, 2 * top + 1, boundary);
exchangeSmall(arr, top, 2 * top + 2, boundary);
}
/**
* 与子节点比较，并调整子堆为小根堆
*/
private void exchangeSmall(int[] arr, int top, int sub, int boundary) {
if(sub > boundary) return;
if(arr[sub] < arr[top]){
swap(arr, top, sub);
adjustSmall(arr, sub, boundary);
}
}
/**
* 交换数组中的两个元素
* 注：此种方法有一个缺陷，i 不可与 j 相等
*/
private void swap(int[] arr, int i, int j) {
if (i == j) return;
arr[i] += arr[j];
arr[j] = arr[i] - arr[j];
arr[i] = arr[i] - arr[j];
}
|
4. JDK提供的堆结构
在Java 1.5版本后就提供了一个具备了小根堆性质的数据结构，也就是优先队列PriorityQueue。
PriorityQueue中的主要方法：
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
|
// 存放元素的数组， 可见堆的存储结构是数组
transient Object[] queue;
// 存放 priority queue被修改的次数
transient int modCount;
/**
* 这是PriorityQueue的其中一个构造方法，由于PriorityQueue默认是小根堆，因此可以通过自己传入comparator来实现大根堆
*/
public PriorityQueue(Comparator<? super E> comparator) {
this(DEFAULT_INITIAL_CAPACITY, comparator);
}
/**
* 添加元素到堆中
*/
public boolean offer(E e) {
if (e == null)
throw new NullPointerException();
modCount++;
int i = size;
// 元素数量超过队列长度，需要扩容
if (i >= queue.length)
grow(i + 1);
// 把e插入到i位置处
siftUp(i, e);
size = i + 1;
return true;
}
/**
* 弹出堆顶元素
*/
public E poll() {
final Object[] es;
final E result;
// 堆顶即为数组中的第一个元素
if ((result = (E) ((es = queue)[0])) != null) {
modCount++;
final int n;
final E x = (E) es[(n = --size)];
es[n] = null;
if (n > 0) {
final Comparator<? super E> cmp;
// 重新调整堆
if ((cmp = comparator) == null)
siftDownComparable(0, x, es, n);
else
siftDownUsingComparator(0, x, es, n, cmp);
}
}
return result;
}
|