一,树的概念

1,树的概念

树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合。

把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。

有一个特殊的结点,称为根结点,根结点没有前驱结点

除根结点外,其余结点被分成M(M>0)个互不相交的集合

T1、T2、……、Tm,其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱,可以有0个或多个后继

因此,树是递归定义的

注意:树形结构中,子树之间不能有交集,否则就不是树形结构

2,树的相关概念

3,二叉树的概念

一棵二叉树是结点的一个有限集合,该集合:

1. 或者为空

2. 由一个根结点加上两棵别称为左子树和右子树的二叉树组成

1. 二叉树不存在度大于2的结点

2. 二叉树的子树有左右之分,次序不能颠倒,因此二叉树是有序树

注意:对于任意的二叉树都是由以下几种情况复合而成的: 

特殊的二叉树:

1. 满二叉树:一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是 说,如果一个二叉树的层数为K,且结点总数是 ,则它就是满二叉树。

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

 

 节点与高度关系

设高度为h,节点个数为N  

 

4,堆的概念

如果有一个关键码的集合K = { , , ,…, },把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中,并满足: = 且 >= ) i = 0,1, 2…,则称为小堆(或大堆)。将根结点最大的堆叫做最大堆或大根堆,根结点最小的堆叫做最小堆或小根堆。  

物理:数组

逻辑:完全二叉树

堆的性质

堆中某个结点的值总是不大于或不小于其父结点的值;

堆总是一棵完全二叉树。

二,堆的实现

老规矩建立三个文件 Heap.c Heap.h Test.c

 1,堆的结构

typedef int HPDataType;

typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;

2,堆的初始化

void HPInit(HP* php);

void HPInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->capacity = php->size = 0;
}

3,堆的销毁

void HPDestroy(HP* php);

void HPDestroy(HP* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;
	php->size = php->capacity = 0;
}

4,数据的交换

 void Swap(HPDataType* p1, HPDataType* p2);

void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

5,向上调整(小堆为例)

void AdjustUp(HPDataType* a, int child);

void AdjustUp(HPDataType* a, int child)
{
	// 初始条件
	// 中间过程
	// 结束条件
	int parent = (child - 1) / 2;
	//while (parent >= 0)
	while (child > 0)
	{
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

条件while (parent >= 0) 不准确,由于child==0时,parent = (child - 1) / 2;是整型还是为0,故可以实现 

6,堆的插入

void HPPush(HP* php, HPDataType x);

判断空间是否足够

if (php->size == php->capacity)
	{
		int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(php->a, newcapacity * sizeof(HPDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}

插入数据

php->a = tmp;
		php->capacity = newcapacity;
	}

	php->a[php->size] = x;
	php->size++;

调整数据

AdjustUp(php->a, php->size - 1);

总代码

void HPPush(HP* php, HPDataType x)
{
	assert(php);

	if (php->size == php->capacity)
	{
		int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(php->a, newcapacity * sizeof(HPDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}

		php->a = tmp;
		php->capacity = newcapacity;
	}

	php->a[php->size] = x;
	php->size++;

	AdjustUp(php->a, php->size - 1);
}

 

 

 

  

7,堆的删除(删除堆顶)

挪动覆盖删除堆顶数据,会导致堆的关系错误

可以将堆顶数据和堆尾数据互换,这样其两个左右子树还是小堆,然后使用向下调节算法 

 

void HPPop(HP* php);

void HPPop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	Swap(&php->a[0], &php->a[php->size-1]);
	php->size--;

	AdjustDown(php->a, php->size, 0);
}

8,向下调整(小堆为例) 

 void AdjustDown(HPDataType* a, int n, int parent);

void AdjustDown(HPDataType* a, int n, int parent)
{
	// 先假设左孩子小
	int child = parent * 2 + 1;

	while (child < n)  // child >= n说明孩子不存在,调整到叶子了
	{
		// 找出小的那个孩子
		if (child + 1 < n && a[child + 1] < a[child])
		{
			++child;
		}

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

 9,取堆顶数据

HPDataType HPTop(HP* php);

HPDataType HPTop(HP* php)
{
	assert(php);
	assert(php->size > 0);

	return php->a[0];
}

10,判断堆是否为空

bool HPEmpty(HP* php);

bool HPEmpty(HP* php)
{
	assert(php);

	return php->size == 0;
}

 三,堆的应用

利用堆排序

向上调整建堆

for (int i = 1; i < n; i++)
	{
		AdjustUp(a, i);
	}

 向下调整建堆

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

完整代码

void HeapSort(int* a, int n)
{
	// 降序,建小堆
	// 升序,建大堆
	/*for (int i = 1; i < n; i++)
	{
		AdjustUp(a, i);
	}*/

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

	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		--end;
	}
}

 

不可以用大堆进行降序,因为首先第一个定死了,后面接着用大堆会使关系错乱

建堆时间复杂度 

向下调整

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

 

向下调整建堆 O(N) 

向上调整

 

向上调整建堆O(N*logN)

n个数找最大的前K个

方法一

建一个N个数的大堆  O(N)

pop k次 O(K*logN)

方法二

用前k个数 建一个小堆 O(K)

剩下的数跟堆顶数据比较,如果比堆顶数据大,就替代堆顶数据进堆(覆盖跟位置然后向下调整)

O(log K*(N-K))

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部