优先队列（堆）

发表于 | | 阅读次数:

优先队列也就是我们常说的小根堆，它至少支持两种操作：插入，删除最小者，它的一种实现方式是二叉堆。

二叉堆

二叉堆具有结构性和堆序性，所谓结构性，是指二叉堆是一颗完全二叉树，而堆序性是指根节点的值应该是最小的。其实堆有一个递归的定义方式：1）堆的根小于它的左右子孩子，2）它的左右子树也是堆。

堆既然是一颗完全二叉树，那么我们就可以用数组的方式来存储堆，而下标的值则已经蕴含了父子关系的信息，如果从1开始存储的话，比如任意位置i上的元素，那么它的左孩子在2i位置上，右孩子在2i+1位置上。
基本操作

插入

将新的节点x插入到二叉堆的最后一个位置size+1处，那么需要对插入的元素进行上滤来确定其最终位置，上滤的过程是调整新插入的节点，使得整个二叉堆保持堆序性质。其实现方式如下

1
2
3
4
5
6
7
8
9
描述：二叉堆插入
输入：二叉堆数组array[],含有的元素个数,待插入的值x
输出：调整好的二叉堆数组
array[0]=x,哨兵值
hole=size+1，当前位置
循环直至x>array[hole/2]//当插入的节点大于父节点的值
	array[hole]=array[hole/2]//将hole处的值复制成父节点的值
	hole=hole/2
array[hole]=x //找到的最终位置

java代码实现如下

1
2
3
4
5
6
7
8
9
10
11
12
public void insert(T x) {
	if(currentSize==array.length-1) {//0位置空出，从1开始放
		enlargeArray(array.length*2+1);
	}
	int hole= ++currentSize;
	array[0]= x;//作为哨兵值，在hole变成1时起作用
	while(x.compareTo(array[hole/2])<0) {//若当前节点的小于父节点
		array[hole]=array[hole/2];
		hole/=2;
	}//while循环实现上滤
	array[hole]=x;//放到最终位置上
}

下滤

插入过程是使用的上滤的过程，而像删除堆顶元素，从已有的数组初始建堆等操作都是通过下滤来实现的，下滤的过程和上滤的稍又不同，具体思路如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
描述：给定堆指定位置，实现向下调整的过程
输入：堆数组array，当前位置size，要调整的位置position
输出：调整好的堆
tmp=array[position]//取出要调整的值
循环当position的左孩子lchild存在时
	当lchild+1存在并且array[lchild+1]<array[lchild]时
		选中较小的孩子和父节点比较，littleChild=lchild+1
	如果array[littleChild]<temp
		array[position]=array[littleChild]
	否则
		结束循环
	position=littleChild
array[position]=tmp//找到最终位置，结束

其Java实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public void percolateDown(int hole) {
	int child;//用于存储将要替换的位置
	T tmp=array[hole];//取出hole位置的值
	while(hole*2<=currentSize) {
		child=hole*2;//左孩子位置
		if(child!=currentSize&&array[child+1].compareTo(array[child])<0)//右孩子存在，且左孩子
			child++;//选择较小的左孩子
		if(tmp.compareTo(array[child])>0) {
			array[hole]=array[child];
		}else {
			break;
		}
		hole=child;
	}
	array[hole]=tmp;
}

初始建堆实现Java,其实其过程是从第一个非叶子节点开始逐步往上进行下滤操作

1
2
3
4
5
6
7
8
/**
 * 初始建堆采用从底往上对已有的树结构进行下滤
 */
public void buildHeap() {
	for(int i=currentSize/2;i>0;i--) {//从第一个非叶子节点的节点进行下滤
		percolateDown(i);
	}
}

删除堆顶元素（最小值）,操作方法是将最后一个节点的值搬到堆顶，然后对堆顶元素进行下滤调整

1
2
3
4
5
6
7
8
9
10
11
/**
	 * 删除堆顶元素
	 */
	public T deleteMin() {
		if(currentSize==0)
			throw new EmptyStackException();
		T minItem=array[1];
		array[1]=array[currentSize--];
		percolateDown(1);
		return minItem;
	}

全部源码

请点击这里

其他的一些思考

一个堆所蕴含的序信息很少，我们除了知道根的值小于左右子树的值以外没有任何其他信息，比如说左右孩子的序，这是堆的性质决定的，对比二叉排序树，堆更像是一个减弱版的二叉排序树，但是实现起来却比二叉排序树简单，没有那么多限制，这也决定了它们的应用场景不一样。

其他的堆

d-堆

每个根节点有d个孩子，d=2时就是二叉堆

左式堆

为支持二叉堆进行合并操作应运而生。
任意节点x零路径长npl是x到一个不具有连个儿子节点的最短路径长，也就是到null节点的最短距离，没有两个儿子的节点的零路径长是0.
左式堆要保持的性质是：是对于堆中的任何一个节点x，它的左儿子的零路径长要大于等于右儿子的零路径长。这个性质使得它更偏向于加深左子树的高度。
其实现合并两个左式堆H1,H2的方法是：如果两个堆其中一个是空的，我们就返回另一个；否则合并两个堆，合并堆的方式是递归的将较大根值的堆与较小根治堆的右子堆进行合并，合并完成后作为较小堆的右子堆，如果合并完成后右子堆的零路径长大于左子堆的零路径长，则交换左右子堆，并更新根节点的零路径长。

斜堆

是左式堆的一种自我调整形式

二项队列

二项队列是堆序的树的集合，也就是森林。每颗堆序树都是右约束的形式，叫做二项式树，高度为k的树恰好有2^k个节点。例如，大小为13的堆可以用森林B3,B2,B0表示，可以将其表示成二进制树1101。

坚持原创技术分享，您的支持将鼓励我继续创作！