数据结构与算法(14)_堆

发表于 | 分类于

介绍

“堆”(Heap) 是一种特殊的树,它的应用场景非常多,最经典的莫过于堆排序.堆排序是一种原地的,时间复杂度为O(nlogn)的排序算法.

如何理解”堆”

什么样的树才是堆?需要满足两点要求:

  • 堆是一个完全二叉树
  • 堆中的每一个节点的值都必须大于等于(或小于等于)其子树中每个节点的值

对于每个节点的值都大于等于子树中每个节点的值的堆,我们叫做”大顶堆”;对于每个节点的值都小于等于子树中每个节点的值的堆,我们叫做”小顶堆”.

//TODO 图25

其中1,2是”大顶堆”,3是”小顶堆”,4不是堆.对于同一种数据,我们可以构建不同的堆形态.

如何实现一个堆

完全二叉树比较适合用数组来存储,如图一个用数组存储堆的例子:

//TODO 图26

从图中可以看到,数组中下标为i的节点的左子节点,就是下标为i 2的节点,又子节点就是下标为i 2 + 1的节点,父节点就是下标为i/2的节点.

往堆中插入一个元素

往堆中插入一个元素后,我们需要满足堆的两个要求.

如果我们把新插入的元素放到堆的最后,如图,已经不符合堆的特性了,于是我们需要进行调整,让其重新满足特性这个过程就叫堆化.

//TODO 图27

堆化有两种方式,从下往上和从上往下.

堆化_从下往上

堆化非常简单就是顺着节点所在的路径向上或者向下,对比,然后交换.

我们可以让新插入的节点与父节点比较大小.如果不满足子节点小于等于父节点的要求,我们就互换两个节点.一直重复这个过程,直到父子节点之间的关系满足.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Heap{
	private int[] a; //数组a,从下标1开始存储数据
	private int n;   //堆可以存储的最大数据
	private int count; //堆中已经存在的数据个数

	public Heap(int capacity){
		a = new int[capacity + 1];
		n = capacity;
		count = 0;
	}

	public void insert(int data){
		if(count >= n) return;
		++count;
		a[count] = data;
		int i = count;
		while(i/2 > 0 && a[i] > a[i/2]){
			swap(a, i, i/2); //用于交换下标为 i 和 i/2 的两个元素
			i = i/2;
		}
	}
}

删除对顶元素

从堆的第二条定义中,任何节点的值都大于等于(或小于等于)子树节点的值,我们可以发现堆顶元素存储的就是最大值或最小值.

假设我们构造的是大顶堆,堆顶元素就是最大元素,当我们删除堆顶元素后,就需要把第二大元素放在堆顶,那第二大元素肯定会出现在左右子节点中.然后我们再迭代的删除第二大节点,以此类推直到叶子节点被删除.不过这种方法有点问题,就是最后堆化出来的堆并不满足完全二叉树的特性.

实际上,我们需要改变一下思路,来解决这个问题.我们把最后一个节点放在堆顶,然后利用同样的父子节点对比方法.对于不满足父子节点大小关系的,互换两个节点,并且重复执行这个过程,直到父子节点满足大小关系为止.这就是从上往下的堆化方法.

//TODO 图28

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public void removeMax(){
	if(count == 0) return;
	a[1] = a[count];
	--count;
	heapify(a, count, 1);
}

public void heapify(int[] a, int n, int i){
	while(true){
		int maxPos = i;
		if(i*2 <= n && a[i] < a[i*2]) maxPos = i * 2;
		if(i*2+1 <=n && a[maxPos] < a[i*2+1]) maxPos = i*2 +1;
		if(maxPos == i) break;
		swap(a, i, maxPos);
		i = maxPos;
	}
}

我们知道,一个包含n个节点的安全二叉树,树的高度不会超过$$log_2n$$.堆化的过程是顺着节点所在的路径来比较交换的,所以堆化的时间复杂度跟树的高度成正比,也就是O(logn).插入数据和删除堆顶数据主要逻辑就是堆化,所以往堆中插入一个数据和删除堆顶数据的时间复杂度都是O(logn).

如何基于堆实现排序

我们可以把堆排序的过程大致拆分成两个步骤,建堆和排序.

建堆

我们首先将数组原地建成一个堆.建堆过程有两种思路.

第一种就是借助插入元素的思路.尽管数组中包含n个数据但是我们可以假设,起初堆中只包含一个数据,就是下标为1的数据,然后我们调用插入操作,将下标从2到n的数据依次插入到堆中.

第二种跟第一种截然相反.第一种建堆思路的处理过程是从前往后处理数组数据,并且每个数据插入堆中时,都是从下往上堆化.而第二种是从后往前处理数组,并且每个数据都是从上往下堆化.

//TODO 图29,30

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
private static void buildHeap(int[] a, int n){
	for(int i = n/2; i >= 1; --i;){
		heapify(a, n, i);
	}
}

private static void heapify(int[] a, int n, int i){
	while(true){
		int maxPos = i;
		if(i*2 <= n && a[i] < a[i*2]) maxPos = i*2;
		if(i*2+1 <= n && a[maxPos] < a[i*2+1]) maxPos = i*2+1;
		if(maxPos == i) break;
		swap(a, i, maxPos);
		i = maxPos;
	}
}

这段代码中,我们队下标从n/2开始到1的数据进行堆化,下标是 n/2+1 到 n 的节点是叶子节点我们不需要堆化,实际上对于完全二叉树来说,下标从 n/2+1 到 n 的节点都是叶子节点

建堆的时间复杂度是O(n);

排序

建堆完成后,数组中的数据已经是按照大顶堆的特性来组织的.数组的第一个元素就是堆顶,也是最大元素.我们把它跟最后一个数组交换,那最大元素就放到了下标为n的位置.

这个过程有点类似”删除堆顶的操作”,当堆顶元素移除之后,我们把原先下标为n的元素放到堆顶,然后再通过堆化方法,将剩下n-1个数据重新构成堆.重复此过程,直到最后堆中只剩下下标为1的一个元素,排序就完成了.

//todo 图31

1
2
3
4
5
6
7
8
9
10
//n表示数据的个数,数组a 中的数据从下标1到n的位置
public static void sort(int[] a, int n){
	buildHeap(a,n);
	int k = n;
	while(k > 1){
		swap(a,1,k);
		--k;
		heapify(a,k,i);
	}
}

整个排序过程中,都只需要极个别的临时存储空间,所以堆排序是原地排序算法.堆排序包括建堆和排序两个操作,建堆过程的时间复杂度是O(n),排序过程的时间复杂的度是O(nlogn),所以堆排序整体的时间复杂度是O(nlogn).

堆排序不是稳定的排序算法,因为在排序的过程中,存在将堆的最后一个节点跟堆顶节点互换的操作.

实际开发中为什么快速排序比堆排序性能好

堆排序数据访问的方式没有快速排序友好.

对于快速排序来说,数据是顺序访问的而对于堆排序来说,数据是跳着访问的.

对于同样的数据,堆排序算法的交换次数要多余快速排序

堆的应用

应用一: 优先级队列

优先级队列.首先,它是一个队列,队列的最大的特性就是先进先出.不过在优先级队列中数据的出队顺序不是先进先出,而是按照优先级来,优先级最高的优先出队.

用堆来实现优先级队列是最直接,最高效的,这是因为堆和优先级队列非常相似.一个堆就可以看作一个优先级队列.它们只是概念上的区分而已.往优先级队列中插入一个元素就相当于往堆中插入一个元素;从优先级队列中取出优先级最高的元素,就相当于取出栈顶元素.

优先级队列的应用场景非常多.比如,赫夫曼编码,图的最短路径,最小生成树的算法等.不仅如此,很多语言中,都提供了优先级队列的实现,比如Java中的PriorityQueue,C++中的priority_queue.

合并有序小文件

假设有100个小文件,每个文件的大小都是100MB,每个文件中存储的都是有序字符串.我们希望将这100个文件合并成一个有序的大文件.这就需要用到优先级队列.

整体思路有点像归并排序中的合并函数.我们从这100个文件中各取第一个字符串放入数组中,然后比较大小,把最小的字符串放入合并后的大文件中,并从数组中删除.

假设,这个最小字符串来自于13.txt这个文件,我们就再从这个小文件取下一个字符串,并且放到数组中,重新比较大小,并且选择最小的放入合并后的大文件,并将它从数组中删除.依次类推,直到所有文件中的数据都放入到大文件为止.

这里我们用的是数组这种数据结构,来完成上述操作,显然这不是很高效.怎样提高效率呢?

这就可以使用优先队列,也可以说是堆.我们将从小文件中取出的字符串放入到小顶堆中,那堆顶的元素,也就是优先级队列队首的元素,就是最小的字符串,我们将这个字符串放入到大文件中,并将其从堆中删除.然后再从小文件中,取下一个字符串,放入堆中.循环这个过程就可以将100个小文件合并成一个大文件.

高性能定时器

假设我们有一个定时器,定时器中维护了多个定时任务,每个定时任务设置了一个要触发执行的时间点.定时器每过一个很小的单位时间(比如1秒),就扫描一遍任务,看是否有任务到达了执行的时间,如果有就执行.

但是,这样每过一秒就扫描一遍任务列表的做法比较低效.主要原因有两点,第一,任务约定的执行时间离当前时间可能还要很久,这样前面多次的扫描都是徒劳的;第二每次都要扫描整个任务列表,如果列表很大的话,比较耗时.

针对上边这些问题,我们可以用优先级队列来解决.我们按照任务设定的执行时间,将这些任务存储在优先级队列中,队列首部(也就是小顶堆的堆顶)存储的是最先执行的任务.

这样,定时器就不需要每隔1秒就扫描一遍任务列表了.它拿队首任务的执行时间点,与当前时间点,相减,得到一个时间间隔T.

这个时间间隔T就是,从当前时间开始,需要等待多久,才会有第一个任务需要被执行.这样定时器就可以设定在T秒之后,再来执行任务.从当前时间点(T-1)秒这段时间里,定时器都不需要做任何事.

当T秒时间过去后,定时器取优先级队列队首的任务执行.然后再计算新的队首任务的执行时间间隔与当前时间的差值,把这个值作为定时器执行下一个任务需要等待的时间

应用二: 利用堆求TopK

我们把求TopK的问题分成两类.一类是针对静态数据集合,也就说数据集合提前确定,不会改变.另一类是针对动态数据集合.

针对静态数据,如何在一个包含n个数据的数组中,查找前k大数据呢?我们维护一个大小为K的小顶堆,顺序遍历数组,从数组中取出数据与堆顶元素比较.如果比堆顶元素大,我们就把堆顶元素删除,并且将这个元素插入到堆中;如果比堆顶元素小,则不出理,继续遍历数组.

遍历数组的时间复杂度是O(n),一次堆化操作的时间复杂度是O(logK),所以最坏的情况下,n个元素都入堆一次,时间复杂度是O(nlogk).

针对动态数据求TopK.例如一个数据集合中有两个操作,一个是添加操作,一个是询问当前K大数据.

如果每次询问K大数据,我们都基于当前数据计算的话,那时间复杂度就是O(nlogK),n表示当前数据的大小.实际上我们可以一直维护一个K大小的小顶堆,当有数据添加到集合中时,我们就拿它与堆顶元素对比.如果比堆顶元素大,我们就把堆顶元素删除,并且将这个元素插入到堆中;如果比堆顶元素小,则不做处理.这样无论何时何时查询当前K大数据,我们都可以立即返回.

应用三: 求中位数

中位数,就是处在中间位置的那个数.如果数据的个数是奇数,把数据从小到大排列那第 n/2 + 1 个数据就是中位数.如果是偶数,那出于中间位置的有两个,第 n/2 和第 n/2+1 个数据,这时候可以任意取一个作为中位数.

对于一组静态数据,中位数是固定的,先排序,第 n/2 个数就是中位数,每次询问中位数,直接返回这个值就好了.所以,尽管排序的的代价比较大,但是边际成本会很小.

对于动态数据,中位数在不停的变动,如果还是先排序的方法,那每次询问中位数,都要先排序,那效率就不高了.

借助堆这种数据结构,我们不用排序,就可以非常高效的实现求中位数操作.

我们维护两个堆,一个大顶堆,一个小顶堆.大顶堆中存储前半部分数据,小顶堆中存储后半部分数据,且小顶堆的数据都要大于大顶堆中的数据.

也就是说n个数据,n是偶数,我们从小到大排序,那前 n/2 个数据存储在大顶堆中,后 n/2 个数据存储在小顶堆中.这样大顶堆中的堆顶元素就是我们要找的中位数.如果n是奇数,情况类似,大顶堆中就存储 n/2+1 个数据,小顶堆中就存储 n/2 个数据.

我们前面也提到,数据是动态变化的,当新添加一个数据之后,我们如何调整这两个堆呢.

如果新加入的数据小于等于大顶堆的堆顶元素,我们就将这个数据插入到大顶堆;如果新添加的数据大于等于小顶堆的堆顶元素,就将这个数据插入到小顶堆.

这个时候,就会出现,两个堆中的数据个数不符合前面的约定情况.这个时候我们可以从一个堆中不停的将堆顶元素移动到另一个堆.

//TODO 图32

于是我们就用两个堆,一个大顶堆,一个小顶堆,实现在动态集合中求中位数的操作.插入数据因为涉及堆化,时间复杂度就变成了O(logn),但求中位数,我们只需要返回大顶堆的堆顶数据就行,时间复杂度是O(1).

实际上,利用两个堆还可以求出其他百分位的数据,原理类似求中位数.例如如何快速求接口的99% 响应时间