二叉树（四）

二叉树的顺序结构及堆的实现

二叉树的顺序结构

普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费，而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储。

需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，这里的堆指的是数据结构，而操作系统虚拟进程地址空间中的堆是操作系统中管理内存的一块区域分段。

堆的概念及结构

如果有一个关键码的集合K = {k₀，k₁，k₂……k_n-1}，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：K_i <= K_{2 * i + 1}且K_i <= K_{2 * i + 2}（K_i >= K_{2 * i + 1}且K_i >= K_{2 * i + 2}）i = 0，1，2……，则称为小堆（或大堆）。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

堆的性质：

• 堆中某个节点的值总是不大于或不小于其父节点的值；
• 堆总是一棵完全二叉树

堆的向下调整算法

现在我们给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提：左右子树必须是一个堆，才能调整。（若想将其调整为小堆，那么根结点的左右子树必须都为小堆；若想将其调整为大堆，那么根结点的左右子树必须都为大堆。）

向下调整法的基本思想（以小堆为例）：

从根结点处开始，选出左右孩子中值较小的孩子，让值较小的孩子与其父亲进行比较：

 如果孩子比父亲节点值小，则该孩子与父亲节点进行交换，并将原来孩子节点的位置当作父结点继续向下进行调整，直到调整完成；

 如果孩子比父亲节点值大，就不需要处理了，说明此时调整完成，该树已经是小堆了。

以小堆为例：

int array[] = {27,15,19,18,28,34,65,49,25,37};

向下调整法的代码如下（以小堆为例）：

//交换函数
void Swap(HPDataType* x, HPDataType* y)
{
	HPDataType tmp = *x;
	*x = *y;
	*y = tmp;
}
//堆的向下调整（小堆）
void AdjustDown(HPDataType* a, int n, int parent)
{
	int child = (parent * 2) + 1;//求出左孩子节点
	while (child < n)
	{
		if (child + 1 < n && a[child] > a[child + 1])//找出孩子节点中较小的
		{
			child++;
		}
		//当父结点大小孩子节点时，交换位置并更新父结点和子节点
		if (a[parent] > a[child])
		{
			Swap(&a[parent], &a[child]);//交换
			parent = child;
			child = (parent * 2) + 1;
		}
        //堆已经形成
		else
		{
			break;
		}
	}
}

使用堆向下调整算法，最坏情况下（一直需要交换节点），假设树的高度为h，那么需要交换的次数为h - 1；假设该树的节点个数为N，那么h = log₂(N+1)（按照满二叉树计算），所以可以得出堆的向下调整算法的时间复杂度为：O(log₂N)。

使用堆的向下调整算法需要满足其根结点的左右子树均为大堆或是小堆，那么如何将一个树调整为堆呢？

可以从倒数第一个非叶子节点开始进行向下调整，并且从该节点开始向前依次进行向下调整：第一个非叶子节点也就是最后一个叶子节点的父结点，假设节点个数为n，则最后一个叶子节点下标为n-1，由child = (parent * 2) + 1，可得其父结点的下标为（n-1 -1）/2；

代码（以小堆为例）：

//建堆
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
    AdjustDown(php->a, php->size, i);
}

建堆的时间复杂度：

因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，多几个节点不影响最终结果) ：

由上图计算建堆过程中总的调整次数：T(n) = 1 * (h - 1) + 2 * (h - 2) + ……+2^h-2^ * 1；再通过错位相减法最后求得：T(n) = 1- h + 2^1^ + 2^2^ +

…… + 2^h-1^，等比数列求和得：T(n) = 2^h^ - h - 1，设N是满二叉树的节点个数，由 N = 2^h^ - 1和h = log₂(N + 1)可以求出T(n) = N - log₂(N+1)，则建堆的时间复杂度为O(N)。

总结：

堆的向下调整法的时间复杂度：O(logN)

建堆的时间复杂度：O(N)

堆的向上调整算法

当我们在一个堆的末尾插入一个数据后，如果要继续保持这是个堆，就需要对堆进行调整，需要用到堆的向上调整法。

向上调整法的基本思想（以建小堆为例）：  将插入结点作为目标节点，和其父结点比较，如果目标结点的值比父结点的值小，则将目标结点与父结点进行交换，并将目标结点的父结点当作新的目标结点继续进行向上调整；如果目标结点的值比父结点的值大，则停止向上调整，说明该树已经是小堆。

代码（以小堆为例）：

//交换函数
void Swap(HPDataType* x, HPDataType* y)
{
	HPDataType tmp = *x;
	*x = *y;
	*y = tmp;
}

//堆的向上调整（小堆）
void AdjustUp(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;//求父结点位置
	while (child > 0)//调整到根结点的位置截止
	{
		if (a[child] < a[parent])//孩子结点的值小于父结点的值
		{
			//将父结点与孩子结点交换
			Swap(&a[child], &a[parent]);
			//继续向上进行调整
			child = parent;
			parent = (child - 1) / 2;
		}
		else//已成堆
		{
			break;
		}
	}
}