数据结构-堆

发表于 更新于 分类于 ，

在计算机的世界里，很多的应用场景只需要取得当前数据集中最大或者最小的元素，而对于数据集中其它数据，并不需要他们一定是有序的。堆就是一种帮助我们高效快速获取最大最小元素的数据结构。

堆的概念

堆(heap) 是一个基于树的特殊数据结构，支持插入、删除、查询最值。它满足每一个子树的根节点一定保存着这棵子树中的最值。大根堆保存的就是最大值，小根堆保存的就是最小值。

堆有很多种变体，包括二项式堆、斐波那契堆等，但是最常见的就是二叉堆，所以说堆可以看做一个(完全)二叉树，从另一方面来说，堆是二叉树的数组实现方式。堆的存储可以看成是数组存储的变形。
二叉堆就是一棵满足“堆性质”的完全二叉树。在使用数组来存储堆的情况下，左子节点的下标就是父节点下标乘以2，右子节点的下标就是父节点下标乘以2+1.这样的方法可以推广到k叉堆。针对数组索引从0开始的情况：
\(heapChildLeft = heap[(i+1)*2-1]\)
\(heapChildRight = heap[(i+1)*2]\)

\(heapParent = heap[i/2-1]\)

数据在数组中分层排放，如index = 0为第一层，即根节点，index = 1,2为第二层，index = 3,4,5,6为第三层index = 7,8,9,10,11,12,13,14为第四层...以此类推。 ***

最大堆与最小堆

堆一般用于解决优先队列等优化问题，存储形式一般也是以最大堆和最小堆的形。 * 最大堆就是父节点的值恒大于子节点。最大值存放于根节点。 * 最小堆就是父节点的值恒小于子节点。最小值存放于根节点。

堆的基本操作

堆的主要操有创建、调整(向上或向下调整)、插入、删除等。

堆的创建

堆可以看做是由一个数组转化而来的。因此，堆的创建也可以进行一些转化。 * 第一步，将一个数组里面的元素通过下标按层·排序的方式构建一个完全二叉树 * 第二步，将这个二叉树通过向下调整的方法调整成为最小或最大堆。 ***

堆的调整

向上调整

一般在插入的时候需要用到向上调整，插入数据后原先堆的大小顺序有可能被改变，我们直接将要插入的节点放在最后，由void insert(node temp)实现。然后我们从这个节点开始向上维护堆，由void shiftUp(ll son)实现，让这个节点去到该去的地方，根据大小根堆的不同，调整判断交换的条件。调整方法：
需要调整的只是从该叶子节点到根节点的子树，先找到该节点的父亲节点，对于最小堆，如果小于父亲节点，那么就需要进行向上调整，使其调整之后满足小堆的性质，如此重复多次，直到整个堆都满足小堆的性质。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void shiftUp(ll son)
{
	while(son>1)
	{
		if(heap[son].val<heap[son/2].val)
		{
			swap(heap[son],heap[son/2]);
            son -= 1;
			son >>=1;
		}
		else
			break;
	}
}
void insert(node temp)
{
	heap[++count1]=temp;
	up(count1);
}
### 向下调整 向下调整一般出现在删除的时候，我们直接将要删除的节点和最后的节点交换，并将count1减1，表示最后一个节点被舍弃，由void Remove()实现。然后我们从原来的那个节点的位置开始向上向下维护堆，由void shiftUp(ll son)和void shiftDown(ll fa)实现。调整方法：
将堆中最后一个元素替代堆顶元素，由于堆的元素个数是按下标控制，因此只需要将下标减一就可以将堆中最后一个元素删除此时，如果堆的结构被破坏，只需要进行简单的向下调整就可以使其重新满足小堆的性质，而其时间复杂度只有logN，因此用堆来进行排序也是可以行得通的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void shiftDown(ll fa)
{
	ll son=fa*2;
	while(son<=count1)
	{
		if(son<count1 && heap[son].val>heap[son+1].val)
			son++;
		if(heap[son].val<heap[fa].val)
		{
			swap(heap[son],heap[fa]);
			fa=son;
			son=fa*2;
		}
		else
			break;
	}
}
void Remove(ll p)
{
	heap[p]=heap[count1--];
	up(p);down(p);
}

堆的运用

海量数据topk问题：100亿个数中找出最大的前k个数
方法： 1. 创建一个有k个元素的小堆 2. 利用循环，将最后一个元素和第一个元素进行替换，然后进行向下调整使其满足小堆的性质，如果这个数比根节点都小，那就直接舍弃，否则进行调整，直到这个堆里面所有的数据都是你要找的最大的那几个数为止，这样再进行打印就可以了。