中秋了也要发博客,写完我就出去浪,祝大家中秋快乐~

堆排序问题算是面试中的高频问题了,这个知识点作为基础排序算法会被问,另外还可以继续延伸,比如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 个数问题。

解法思路如下 :

  1. 创建一个大小为 K 的数组 B,并初始化数值为Integer.MAX_VALUE(小顶堆则初始化为Integer.MIN_VALUE
  2. 遍历给定的数组 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);
}
// min k
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问题不同的是,优先队列需要增加一个上浮操作。对于新加入的任务,需要执行该操作来维持堆的有序性。

解决思路如下:

  1. poll的实现堆已经实现过了,参考上文
  2. offer的实现需要使用上浮操作,将新元素增加到队尾,然后执行上浮操作即可保持堆有序性
  3. 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(){
// 默认容量10
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];
}
}

堆排序问题终于写完,该出去浪了~