基本概念
堆是一种数据结构，一种叫做完全二叉树的数据结构。
大顶堆：每个节点的值都大于或者等于它的左右子节点的值。
小顶堆：每个节点的值都小于或者等于它的左右子节点的值。
我们使用数组作为堆数据的存储结构，那么有以下性质
大顶堆：arr[i] >= arr[2i + 1] && arr[i] >= arr[2i + 2]
小顶堆：arr[i] <= arr[2i + 1] && arr[i] <= arr[2i + 2]
排序思想
堆排序的基本思想是：
- 将带排序的序列构造成一个大顶堆，根据大顶堆的性质，当前堆的根节点（堆顶）就是序列中最大的元素；
- 将堆顶元素和最后一个元素交换，然后将剩下的节点重新构造成一个大顶堆；
- 重复步骤2，如此反复，从第一次构建大顶堆开始，每一次构建，我们都能获得一个序列的最大值，然后把它放到大顶堆的尾部。最后，就得到一个有序的序列了。
假设给定的无序序列arr是
4, 5, 8, 2, 3, 9, 7, 1
- 将无序序列构建成一个大顶堆。
首先我们将现在的无序序列看成一个堆结构，一个没有规则的二叉树，将序列里的值按照从上往下，从左到右依次填充到二叉树中。
根据大顶堆的性质，每个节点的值都大于或者等于它的左右子节点的值。所以我们需要找到所有包含子节点的节点，也就是非叶子节点，然后调整他们的父子关系，非叶子节点遍历的顺序应该是从下往上，这比从上往下的顺序遍历次数少很多，因为，大顶堆的性质要求父节点的值要大于或者等于子节点的值，如果从上往下遍历，当某个节点即是父节点又是子节点并且它的子节点仍然有子节点的时候，因为子节点还没有遍历到，所以子节点不符合大顶堆性质，当子节点调整后，必然会影响其父节点需要二次调整。但是从下往上的方式不需要考虑父节点，因为当前节点调整完之后，当前节点必然比它的所有子节点都大，所以，只会最多影响到其中两个孩子当中的一个子节点的二次调整（当调整到某一个子节点满足最大堆时后面就可以不用再调整，因为自下而上之前已经调整过了）。相比之下，从下往上的遍历方式比从上往下的方式少了父节点的二次调整。
那么，该如何知道最后一个非叶子节点的位置，也就是索引值？
对于完全二叉树，每层的元素个数是上一层的2倍，由等比数列通项公式可知到n-1层所有元素个数为$2^{n-1}-1$，第n层元素个数是$2^{n-1}$，所以第n层数目减1刚好等于前面所有层元素个数之和。所以，我们能找到最后一层的第一个节点的索引，即节点总数/2（根节点索引为0），这也就是第一个叶子节点，所以第一个非叶子节点的索引就是第一个叶子结点的索引-1。那么对于填不满的二叉树呢？这个计算方式仍然适用，当我们从上往下，从左往右填充二叉树的过程中，第一个叶子节点，一定是序列长度/2，所以第一个非叶子节点的索引就是arr.length / 2 -1。
现在找到了最后一个非叶子节点arr[3]，即元素值为2的节点，比较它的左右节点的值，是否比他大，如果大就换位置。再比较下一个非叶子节点， 也就是元素2所在下标-1的位置arr[2]， 也就是元素值8，比较左右节点依此类推一直到根节点，根节点调整完后则大顶堆构建完毕。
-
排序序列， 将堆顶元素和尾部元素交换
-
将剩余的元素(可以看成length-1的数组)重新构成大顶堆，现在可以从上到下调整了，因为其他节点之前已经满足大顶堆性质，此时只需要调整堆顶元素即可。
-
重复2和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
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
|
package com.eh.ftd.dsa.ds;
import java.util.Arrays;
import java.util.Random;
/**
* 堆排序
*
* @author David Li
* @create 2020/06/27 21:49
*/
public class HeapSort {
static void sort(int[] arr) {
// 1. 从第一个非叶子节点开始构建大顶堆，一直遍历到根节点，这样整个序列就构建成大顶堆了
for (int i = arr.length / 2 - 1; i >= 0; i--) {
buildHeap(arr, i, arr.length);
}
// 2. 大顶堆构建完毕，进行交换
swap(arr, 0, arr.length - 1);
// 3. 重新构建大顶堆，构建完毕后交换
for (int j = arr.length - 1; j > 0; j--) {
buildHeap(arr, 0, j);
swap(arr, 0, j - 1);
}
}
/**
* 数组i和j 两个元素交换
*
* @param arr
* @param i
* @param j
*/
static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
/**
* 构建大顶堆
*
* @param arr 原始数组
* @param i 从第i个元素开始构建大顶堆
* @param length 剩余元素个数
*/
static void buildHeap(int[] arr, int i, int length) {
int temp = arr[i]; // 有点类似于快排里的挖坑，当子树完成大顶堆排序后会出现一个坑，到时使用temp去填，主要是为了减少交换赋值的次数
// 和左右节点比较，如果左右节点比当前节点值大则交换，继续比较较大节点和较大节点的左右子节点，依次类推直到最后比较叶子节点
for (int j = 2 * i + 1; j < length; j = 2 * j + 1) {
// 如果左子节点小于右子节点，那么只需要比较当前节点和右子节点即可。
if (j + 1 < length && arr[j] < arr[j + 1]) {
j++;
}
if (arr[j] > temp) {
// 将较大的子节点值赋值给当前节点，相当于子节点挖了坑
arr[i] = arr[j];
// 记住坑的位置，最后使用temp去填
i = j;
} else {
// 根据文章说明，我们先构建最后一个非叶子节点的大顶堆，依次类推一直构建到根节点的大顶堆，
// 当整个序列是一个大顶堆后，从上到下遍历，只要当前节点值大于左右子节点的值那么就无需再遍历孙子节点的值，
// 因为后面肯定是满足大顶堆的
break;
}
}
// 将坑填上，用最小的值temp
arr[i] = temp;
}
public static void main(String[] args) {
// int[] arr = {4, 5, 8, 2, 3, 9, 7, 1};
// sort(arr);
// Arrays.stream(arr).forEach(x -> System.out.printf("%d\t", x));
int[] arr = new int[10000000];
Random random = new Random();
for (int i = 0; i < arr.length - 1; i++) {
arr[i] = random.nextInt(100000);
}
long now = System.currentTimeMillis();
sort(arr);
System.out.println(System.currentTimeMillis() - now);
}
}
|
复杂度分析
时间复杂度：nlog(n)
空间复杂度：O(1)。
优先队列和堆
https://www.cnblogs.com/wmyskxz/p/9301021.html
参考
堆排序
