数据结构之【堆详解】_数据结构堆

目录

树概念及结构

树的表示

二叉树概念及结构

二叉树的性质

堆的概念及结构

堆向下调整算法

普通情况建堆

树概念及结构

节点的度： 一个节点含有的子树的个数称为该节点的度； 如上图： A 的为 6

叶节点或终端节点： 度为 0 的节点称为叶节点； 如上图： B 、 C 、 H 、 I... 等节点为叶节点

非终端节点或分支节点： 度不为 0 的节点； 如上图： D 、 E 、 F 、 G... 等节点为分支节点

双亲节点或父节点： 若一个节点含有子节点，则这个节点称为其子节点的父节点； 如上图： A 是 B 的父节点

孩子节点或子节点： 一个节点含有的子树的根节点称为该节点的子节点； 如上图： B 是 A 的孩子节点

兄弟节点： 具有相同父节点的节点互称为兄弟节点； 如上图： B 、 C 是兄弟节点

树的度： 一棵树中，最大的节点的度称为树的度； 如上图：树的度为 6

节点的层次： 从根开始定义起，根为第 1 层，根的子节点为第 2 层，以此类推；

树的高度或深度： 树中节点的最大层次； 如上图：树的高度为 4（第一层从1开始）

【有的书上认为是3，第一层从0开始编号】

堂兄弟节点： 双亲在同一层的节点互为堂兄弟；如上图： H 、 I 互为兄弟节点

节点的祖先： 从根到该节点所经分支上的所有节点；如上图： A 是所有节点的祖先

子孙： 以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是 A 的子孙

森林： 由 m （ m>0 ）棵互不相交的树的集合称为森林，并查集其实就是一个森林

注意：

每一棵树，都是有根节点+多个字树构成，子树也是一样的构成

树的表示

树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，实际中树有很多种表示方式，如：双亲表 示法，孩子表示法、孩子兄弟表示法等等。

我们这里就简单的了解其中最常用的孩子兄弟表示法

图示：

上述表示法，左孩子右兄弟表示法

（从左往右数第一个孩子）

无论树中一个节点有多少个孩子，都可以表示，因为我只指向第一个孩子，剩下的孩子，让孩子之间用兄弟指针串起来

双亲表示法:

图示：

 B和C是A的孩子，他俩存储的是双亲A的下标也就是0，D E F的双亲是B,他们三个存储的是双亲B的下标也就是1，剩下的依次类推。（不实用）

树在实际中的运用

（表示文件系统的目录树结构）

二叉树概念及结构

1 概念

一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根节点加上两棵别称为左子树和右子树 的二叉树组成。

二叉树的特点：

1. 每个结点最多有两棵子树，即二叉树不存在度大于 2 的结点。

2. 二叉树的子树有左右之分，其子树的次序不能颠倒。

数据结构中的二叉树： 

特殊的二叉树：

1. 满二叉树： 一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是 说，如果一个二叉树的层数为K ，且结点总数是 (2^k) -1 ，则它就是满二叉树。

图示：

2. 完全二叉树 ：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为 K 的，有n 个结点的二叉树，当且仅当其每一个结点都与深度为 K 的满二叉树中编号从 1 至 n 的结点一一对 应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。

图示：

但如果是这样那他就不是完全二叉树

意思就是除了最后一层，之前的必须是是满二叉树，最后一层可以不是满的但是最后一层从左到右必须是连续的，  

二叉树的性质

1. 若规定根节点的层数为 1 ，则一棵非空二叉树的 第 i 层上最多有 2^(i-1) 个结点 .

2. 若规定根节点的层数为 1 ，则 深度为 h 的二叉树的最大结点数是 2^h- 1 .

推导过程如图：

3. 对任何一棵二叉树 , 如果度为 0 其叶结点个数为 n0, 度为 2 的分支结点个数为 n2, 则有 n0 ＝ n2 ＋ 1

4.完全二叉树中度为1的节点最多只有一个

5. 若规定根节点的层数为 1 ，具有 n 个结点的满二叉树的深度 ， h=Log2(n+1) . (ps ： Log2(n+1) 是 log 以 2 为 底，n+1 为对数 )

【2^h-1=n,所以 h=Log2(n+1)】

接下来用该性质练练手

1. 某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（

）

A 不存在这样的二叉树

B 200

C 198

D 199

答：根据上述性质 n0=n2+1;

        n0=199+1=200;

2. 在具有 2 n 个结点的完全二叉树中，叶子结点个数为（

）

A n

B n + 1

C n - 1

D n / 2

答：设度为0的结点为n0,度为1的为n1，度为2的为n2

n0+n1+n2=2n

n0+n1+n0-1=2n;（n0=n2+1）

2n0-1+n1=2n;(完全二叉树中度为1的节点最多只有一个，所以n1=1)

2n0=2n;

n0=

选A;

3. 一棵完全二叉树的节点数位为 531 个，那么这棵树的高度为（

）

A 11

B 10

C 8

D 12

答：设高度为h

2^h-1-x=531;(x为最后一层缺的结点的个数）

x的范围[0,2^(h-1)-1];(完全二叉树)

所以将答案往上述两个公示套，发现符合求的是B

如图：这一部分即为x

4. 一个具有 767 个节点的完全二叉树，其叶子节点个数为（）

A 383

B 384

C 385

D 386

 答：

 n2+n1+n0=767；

 n0-1+n1+n0=767;

 2n0+n1=768;(完全二叉树中度为1的节点最多只有一个，所以n1=0,如果n1=1，则n0为小数)

 n0=38 选B;

堆的概念及结构

如果有一个关键码的集合 K = {k0 ， k1 ， k2 ， … ， kn-1} ，把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中，并满足：Ki <= K2 i+1 且 Ki<= K2 i+2 (Ki >= K2 i+1 且 Ki >= K2 i+2) i = 0 ， 1 ， 2… ，则称为 小堆( 或大堆)。

堆就是一个完全二叉树。

堆的存储

堆的存储实际就是一个数组，逻辑结构上是一个完全二叉树

如图：

 将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

小根堆就是父亲小于等于孩子

大根堆是父亲大于等于孩子

堆的公式（孩子与父亲的关系）

父亲的下标是parent

leftchild=parent*2+1;

rightchild=parent*2+2;

parent=(child-1)/2;

如图：

堆向下调整算法

思路：

1. 选出左右孩子中小的那一个数
2.小的这个孩子与父亲比
  a.如果小的孩子比父亲小，则跟父亲交换位置，并且吧原来孩子的位置当成父亲继续往下调整，直到走到叶子节点
 b.如果小的孩子比父亲大，则不需要处理，调整完成，整个树已经是小堆

对这样一个数组{27,15,19,18,28,34,65,49,25,37};调整思路如图 

接下来通过思路实现代码：

void AdjustDown(int* a, int n, int parent)
{
	//找出左右孩子小的那个
	int child = parent * 2 + 1; //左孩子
	while (child < n)
	{
		//找出左右孩子小的那一个
		if (a[child + 1] < a[child])  
		{
			//默认左孩子小，如果右孩子小就++，加到右孩子
			++child;
		}
		if (a[child] < a[parent])
		{
			Swap(&a[parent], &a[child]);
			parent = child;   //孩子成为父亲
			child = parent * 2 + 1;
		}
		else  //b情况
		{
			break;
		}
		
	}
}

 注意看这个代码对上述例子是不会有任何问题的，但是他还存在一个潜在的风险

如果将上面的例子改动一个数字 如图：将28改为16

 那么当他进行到第三步时

 a[child+1]就会发生越界的问题，所以要对a[child+1]进行限制让他小于n，改进后如下

void AdjustDown(int* a, int n, int parent)
{
	//找出左右孩子小的那个
	int child = parent * 2 + 1; //左孩子
	while (child < n)
	{
		//找出左右孩子小的那一个
		if (child + 1 < n && a[child + 1] < a[child])  
		{
			//默认做孩子小，如果右孩子小就++，加到右孩子
			++child;
		}
		if (a[child] < a[parent])
		{
			Swap(&a[parent], &a[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else  //b情况
		{
			break;
		}
		
	}
}

完整代码如下：

#include <stdio.h>
 
void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
 
void AdjustDown(int* a, int n, int parent)
{
	//找出左右孩子小的那个
	int child = parent * 2 + 1; //左孩子
	while (child < n)
	{
		//找出左右孩子小的那一个
		if (child + 1 < n && a[child + 1] < a[child])  
		{
			//默认做孩子小，如果右孩子小就++，加到右孩子
			++child;
		}
		if (a[child] < a[parent])
		{
			Swap(&a[parent], &a[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else  //b情况
		{
			break;
		}
		
	}
}
 
int main()
{
	//前提左右字树是小堆
	int a[] = { 27,15,19,18,28,34,65,49,25,37 };
	int n = sizeof(a) / sizeof(a[0]);
    AdjustDown(a, n, 0);
 
	return 0;
}

运行后发现和我们预期的结果相同 

普通情况建堆

  特殊情况我们可以用向下调整算法，接下来由特殊转为一般，如果左右字树不是小堆，该如何将其调整为堆

eg： 对这样一个数组{15,18,28,34,65,19,49,25,37,27}进行调整

思路：从倒数的第一个非叶子节点（最后一个节点的父亲），从后往前，按照编号，依次作为子树去向下调整

以下就是建堆算法，根据parent=(child-1)/2;最后一个结点的父亲就是  [（n-1）-1  ]  /  2;n代表着数组中元素的个数。而除了最后一个结点的父亲之外，其余父亲结点的编号都是连续的直接减1即可，该建堆算法的时间复杂度是O(N);

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

 完整代码：

#include <stdio.h>
 
void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
 
void AdjustDown(int* a, int n, int parent)
{
	//找出左右孩子小的那个
	int child = parent * 2 + 1; //左孩子
	while (child < n)
	{
		//找出左右孩子小的那一个
		if (child + 1 < n && a[child + 1] < a[child])  
		{
			//默认做孩子小，如果右孩子小就++，加到右孩子
			++child;
		}
		if (a[child] < a[parent])
		{
			Swap(&a[parent], &a[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else  //b情况
		{
			break;
		}
		
	}
}
 
int main()
{
	//前提左右字树是小堆
	int a[] = { 15,18,28,34,65,19,49,25,37,27 };
	int n = sizeof(a) / sizeof(a[0]);
 
	for (int i = (n - 1 - 1) / 2;i >= 0;i--)
	{
		AdjustDown(a, n, i);
	}
	return 0;
}

 效果演示

 以上代码是构造小堆，构造大堆也很简单，只需要将小于改成大于即可,其余不做改变，如下

if (child + 1 < n && a[child + 1] > a[child])  
		{
			
			++child;
		}
		if (a[child] > a[parent])
		{
			Swap(&a[parent], &a[child]);
			parent = child;
			child = parent * 2 + 1;
		}

以上例子构造大堆如下