您现在的位置是：首页 >技术教程 >【数据结构】_堆的结构及向上、向下调整算法网站首页技术教程

目录

1. 堆的概念与结构

2. 入堆及堆的向上调整算法

2.1 入堆HPPush操作

2.3 向上调整AdjustUp操作

3. 出堆及堆的向下调整算法

3.1 出堆HPPop操作

3.2 堆的向下调整算法

1. 堆的概念与结构

1、堆是一个完全二叉树，堆的所有元素按照完全二叉树的顺序存储方式存储在一个一维数组中；

2、堆有两个特点：

（1）堆是完全二叉树；（2）堆中某个结点的值总是不大于或不小于其父结点的值；

3、根结点最大的堆称为大根堆，根节点最小的堆称为小根堆；

本文以小根堆为例。

2. 入堆及堆的向上调整算法

2.1 入堆HPPush操作

由于堆采取完全二叉树的顺序存储方式，在物理存储上仍为一个数组。

将新增元素插入到数组尾，再逐层调整父子结点的大小关系，使其满足小根堆特性；

注：新插入的结点需比较的结点不只是当前的父结点，新插入的结点需与其所有祖先结点进行比较；

2.3 向上调整AdjustUp操作

试以具体例子分析：

1、实现思路

由于向上调整需实现父结点与子结点值的比较，故设下标分别为parent和child，

已知对于顺序存储结构，已知child求parent的公式为：parent = (child-1)/2；

若a[parent]<a[child]，说明已符合小根堆特性，无需调整；

若a[parent]>a[child]，则交换二者，并将child更新为当前parent，再求新的parent进行比较；

2、关于循环判断条件：

写法1：while ( parent>=0 )：

实际对于整除运算parent = (child - 1) / 2，parent并不会小于0，但当parent=0时，若a[parent] > a[child]，则再次进行child与parent的更新，使得parent与child均为0。再次进入while循环，此时进行的是根结点自身与自身的比较，不符合if条件，通过else分支执行break最终跳出循环；

写法2：while ( child>0 )：

当parent=0时，若若a[parent] > a[child]，则再次进行child与parent的更新，使得child更新为0，下次则无法进入while循环；

相比较而言，写法一能实现向下调整并不符合严谨的逻辑设计。写法二，即令child>0作为循环进行条件是更符合逻辑的；

实现如下：

void Swap(HPDataType* px, HPDataType* py) {
	HPDataType tmp = *px;
	*px = *py;
	*py = tmp;
}
// 向上调整
void AdjustUp(HPDataType* a, int child) {
	int parent = (child - 1) / 2;
	while (child> 0) {
		// 父结点值大于子结点值：交换并更新parent和child
		if (a[parent] > a[child]) {
			Swap(&a[parent], &a[child]);
			child = parent;
			parent = (child - 1) / 2;
		}
		// 父结点值小于子结点值：调整结束
		else {
			break;
		}
	}
}

3. 出堆及堆的向下调整算法

3.1 出堆HPPop操作

pop操作要求删除堆顶元素，若直接删除其物理存储的数组结构的第一个元素，由于堆只限定父子结点大小关系而未限定兄弟结点大小关系，这种删除堆顶元素的方式会导致整个堆结构错位，剩下的元素可能不再是一个小根堆。

pop方法实现的方法为：交换数组的第一个元素和最后一个元素，即交换堆顶结点的值和堆的最底层最右侧的叶结点的值，删除最后一个结点后，再逐层调整父结点与子结点的大小关系，使其满足小根堆特性；

注：1、由于仅交换了堆顶结点和最末的叶结点的值，并未影响中间层的其他结点。故而交换后，除堆顶结点外，其左右子树均满足小根堆特性；

2、HPPop最多只需调整树的高度次，时间复杂度为O(log N)；

3.2 堆的向下调整算法

试以具体例子分析：

1、实现思路

由于向下调整需实现父结点与左右子结点值的比较，记左右孩子中值较小的结点为child，记待调整子树的根结点下标为parent；

对比父结点与子结点中值较小的那个结点的大小，并逐层进行调整：

若a[parent]<a[child]，说明已符合小根堆特性，无需调整；

若a[parent]>a[child]，则交换二者，并将parent更新为当前child，再求新的child进行比较；

2、关于循环判断条件：

直到child大于堆的最末叶结点的下标，即child>size-1（等价于child>=size）时，表示已经向下查找到叶结点了，循环即终止。故循环判断条件为while(child<size)；

完整实现：

void Swap(HPDataType* px, HPDataType* py) {
	HPDataType tmp = *px;
	*px = *py;
	*py = tmp;
}
void AdjustDown(HPDataType*a, int n, int parent) {
	// 假设法：假设左孩子更小
	int child = parent * 2 + 1;
	// child=n表示已经遍历到最后的叶结点
	while (child < n) {
		// 确定左右孩子中更小的
		if (child+1<n && a[child] > a[child + 1]) {
			child++;
		}
		// 若子结点小于父结点，则交换并更新parent和child
		if (a[child] < a[parent]) {
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else {
			break;
		}
	}
}