中秋了也要发博客，写完我就出去浪，祝大家中秋快乐~
堆排序问题算是面试中的高频问题了，这个知识点作为基础排序算法会被问，另外还可以继续延伸，比如Top K问题和实现优先队列。百度面试的时候就让实现优先队列，然而当时紧张没有写出来，其实还是很简单的。
堆的定义
堆是一种数据结构，类似于完全二叉树，但一般使用数组作为堆的实现。堆分为大顶堆和小顶堆，大顶堆指父节点的值大于两个孩子节点的值，这样根节点的值必定为整个堆的最大值，因此称为大顶堆；与此相反，小顶堆指父节点的值小于两个孩子节点的值，这样根节点的值必定为整个堆的最小值，因此称为小顶堆。
大顶堆和小顶堆
主要操作
| 方法 |
作用 |
时间复杂度 |
| get |
取得堆顶值 |
O(1) |
| sink |
将元素下沉，恢复堆有序性 |
O(logn) |
| delete |
删除并取得顶堆值 |
O(logn) |
| build |
建堆 |
O(n) |
具体实现
这里以大顶堆作为例子，小顶堆其实类似，只不过下沉操作的时候比较大小时更换一下即可。
下沉操作
这是堆排序中最重要的操作，它保证了堆的有序性，建堆和删除堆顶值的时候都需要调用这个操作。
下沉操作主要是让当前节点和两个子节点进行比较，如果父节点比子节点小，则将这两个节点互换，重复这个操作直至父节点比子节点大。代码如下：
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
|
private void sink(int [] nums, int i, int end) {
while (i < end) {
int child = child(i);
if (child < end) {
if ((child + 1 < end) && nums[child] < nums[child + 1]) {
child ++;
}
if (nums[i] < nums[child]) {
swap(nums, i, child);
i = child;
} else {
break;
}
} else {
break;
}
}
}
private int child(int i) {
return i * 2 + 1;
}
private void swap(int [] nums, int i, int j){
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
|
建堆过程
建堆其实就是不断调用sink下沉的过程，给定初始的数组，只需要从最后一个数字开始往前不断进行下沉操作即可，类似于一个递推的过程，不断的将新元素插入到原先已经建好堆的后方数组中。代码如下
1
2
3
4
5
6
| public void heapSort(int [] nums) {
for(int i = nums.length - 1; i >= 0; i --) {
sink(nums, i, nums.length);
}
}
|
获取堆顶值
此时数组第一位为堆顶值，最大，直接返回即可
1
2
3
4
| public int getMax(){
return nums[0];
}
|
移除堆顶值
移除数组第一位，并将数组最后一个数移到堆顶，并执行下沉操作即可保持堆有序性。
1
2
3
4
5
6
| public int delMax(int [] nums, int len){
int tmp = nums[0];
swap(nums, 0, len - 1);
sink(nums, 0, len - 1);
return tmp;
}
|
问题扩展
Top K 问题
Top K问题是堆排序的扩展，一般问题描述如下：
给定一个数组，求出最小/最大的 K 个数
这个问题最简单的解决方法就是排序，时间复杂度最优是O(nlogn)，此法不是本文重点，不在此详细说明。这个问题用堆可以很容易的解决，最小 K 个数可以使用大顶堆，最大 K 个数可以使用小顶堆，本文示例使用大顶堆解决最小 K 个数问题。
解法思路如下 ：
- 创建一个大小为 K 的数组 B，并初始化数值为
Integer.MAX_VALUE（小顶堆则初始化为Integer.MIN_VALUE）
- 遍历给定的数组 A，对于每一个数 C，将其跟 B 的堆顶进行比较，如果比堆顶小，则将 B 的堆顶值替换成 C，然后执行下沉操作。遍历完成之后 B 数组即为所求的数字。
代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| public int [] topK(int [] nums, int k) {
if (k > nums.length) {
throw new IllegalArgumentException("k:" + k + ", length:" + nums.length);
}
int [] top = new int[k];
for (int i = 0; i < top.length; i++) {
top[i] = Integer.MAX_VALUE;
}
for (int i = 0; i < nums.length; i ++) {
if (nums[i] < top[0]) {
top[0] = nums[i];
sink(top, 0, top.length);
}
}
return top;
}
|
优先队列
优先队列在队列调度的时候用的很多，主要实现一个需求，往优先队列中无序放入优先级不同的任务，要求随时能取出优先级最高的任务。使用大顶堆堆可以很好的满足这个要求。大顶堆能维持顶堆的优先级最高，随时能够取出该任务。
主要API如下：
| 方法 |
作用 |
时间复杂度 |
| poll |
取出优先级最高的任务 |
O(logn) |
| offer |
增加一个任务 |
O(logn) |
| isEmpty |
查询队列是否为空 |
O(1) |
| getSize |
查询队列大小 |
O(1) |
| clear |
清空队列 |
O(1) |
与上述Top K问题不同的是，优先队列需要增加一个上浮操作。对于新加入的任务，需要执行该操作来维持堆的有序性。
解决思路如下：
poll的实现堆已经实现过了，参考上文offer的实现需要使用上浮操作，将新元素增加到队尾，然后执行上浮操作即可保持堆有序性isEmpty的实现可以通过保存队列当前元素数量来实现
具体代码如下：
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
| public class PriorityQueue<T implements Comparable>{
private final int DEFAULT_COMPACITY = 10;
private int size = 0;
private int compacity = 0;
private T [] ts;
public PriorityQueue(){
this(DEFAULT_COMPACITY);
}
public PriorityQueue(int com){
compacity = com;
ts = new T[compacity];
}
public T poll(){
T t = ts[0];
swap(ts, 0, size - 1);
size --;
sink(ts, 0, size + 1);
return t;
}
public boolean offer(T t){
if(size >= compacity) {
return false;
}
size ++;
ts[size - 1] = t;
up(size - 1);
return true;
}
public boolean isEmpty(){
return size == 0;
}
public int getSize(){
return size;
}
private void sink(int i){
}
private void up(int i) {
while(i > 0) {
int parent = i / 2;
if(ts[i].compareTo(ts[parent] > 0)) {
swap(ts, i, parent);
i = i / 2;
} else {
break;
}
}
}
public void clear(){
size = 0;
ts = new T[compacity];
}
}
|
堆排序问题终于写完，该出去浪了~
最后更新时间：
