【C++】树？堆？怎么实现？

新的一周过去了，大家有没有对上星期练习的题目更加熟练呢？

上星期和上上星期我们主要学习了顺序表，链表，和用这俩都能实现的栈和队列

那么今天我们看看堆又是什么结构

目录

1.树 介绍

2.堆 介绍

3.堆的实现

---

1.树の介绍

不就是树，谁没见过对吧

那么类似的计算机也有一种树，很像我们学过的树状图

为了规范使用，先定义一些名称

层数和高度如你所见 就是你理解的意思

其实我们发现，这个命名规则就很像遗传族谱，其中也是借用了遗传族谱的一些名称

我们可以类比理解一下兄弟节点，堂兄弟节点，父子节点。。。

节点的祖先，是指从该节点向上走的唯一路径上经历的所有节点都是他的  节点的祖先 

我们规定：树和树之间不能交叉！！！

森林：互不相交的树构成的结构~~

这只是最普通的树，还有一些稍微长得特殊一点的树

二叉树：每个父节点都有两个枝丫

二叉树里面又有两种

满二叉树：每一层都是满的节点

根据等比公式，满二叉树的高度为h（本图是4）那么节点个数就是2^h-1

第k层是满的，那么那一层的节点个数是2^(k-1) ，k从1开始 

完全二叉树：最后一层可以不满，但是前面层数必须满，必须从左到右连续

大家自己去算一下，和刚才的方法一样的

完全二叉树的高度是h，那么总结点最多2^h-1  最少2^(h-1) 

---

还有一些小小的二叉树计算技巧~

1.度为0的节点个数比度为2的节点个数多1

 2.完全二叉树度为1 的节点个数不是0就是1

3.要计算叶子节点个数的题目，就是算度为0，可以假设度为0有N0个，度为1有N1，度为2有N2

再根据 前两个技巧建立方程就好了

---

简单的基础知识就是这么多，那么真的在内存中就是有一块空间存储这些小圈和直线吗？

当然不是！！！！！！

这个树形状的图只是帮助我们人理解的（人家计算机根本不用借助图好吧）

所以这个图就是一种假想的模型，术语叫做 逻辑结构！！！（逻辑不好得用他帮助理解）

---

那么就该思考了，真实的内存结构（术语：物理结构）是什么样子

对于堆 其实是数组~

更复杂的现在不讨论  

---

 那么对于一般的树，他的“遗传图谱”怎么表示出来啊~~~

有个大神，想到了一种很的方法

struct TreeNode
{
int data;
TreeNode* child;
TreeNode* brother; 
};

我们细想一下，如果从最开始的根，我知道他的  孩子节点  和 孩子节点的兄弟节点 

那简直就是完美解决整个图谱

 

直呼大佬 

---

2.堆的介绍

大家肯定在C的时候就对堆耳熟能详，现在我们主要看一下更深层次的理解

 刚才说过，堆他的存放方式是这样的

从0开始编号，是为了和数组从0开始很好的对应

我们可以心里想着左图  但是不能不清楚他的真实结构是右图！！！ 

---

一个随随便便的数组不一定是堆，但是堆一定是一个数组 

给你一个数组怎么判断他到底是不是一个堆？

首先我们要清楚堆的分类

大堆：每一个父节点都比他的子节点大

小堆：每一个父节点都比他的子节点小

所以我们只要看是不是大/小堆其中一种就行

比如数组{1,4,5,8,99} 1比4 5都小，4比8和99都小，所以这就是一个小堆，即堆

从中可以看出，对于数组你能不能一眼看出谁是谁的孩子，是左孩子还是右孩子？很重要

因为堆是完全二叉树 ，所以每个节点最多肯定是2个孩子

第一个数据1一定是根，往下两个4 5就是根（1）的孩子节点，在前面的4是左孩子

8,99是4,5中靠前数据（即4）的孩子节点，同样的8是左孩子

---

 对应上我们刚才学的父子节点，不能拿发现父子节点的下标其实有规律

左孩子下标=父亲下标*2+1    因为左孩子的下标总是奇数！！

右孩子下标=父亲下标*2+2    因为右孩子的下标总是偶数！！

父亲下标=（孩子（左/右）-1）/2

---

3. 堆的实现（重点重点）

 既然我们这么了解堆的结构，那么上手吧

这个实现和顺序表就很相似了

还是定义一个结构体，也就是表示一个节点

a表示结构体指针，可以用指针的方式访问数组

size是数组中元素的个数

capacity是容量，当容量和元素个数相等的时候要考虑扩容（老生常谈了）

把数据类型重定义可以方便以后存放不同类型的数据

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}Heap;
 
//打印
void HeapPrint(Heap* hp);
//交换
void Swap(HPDataType* a, HPDataType* b);
// 堆的构建
void HeapCreate(Heap* hp, HPDataType* a, int n);
//向上调整
void AdjustUp(HPDataType* a, int chirld);
//向下调整
AdjustDown(HPDataType* a, int n, int parent);
//初始化
void HeapInit(Heap* hp);
// 堆的销毁
void HeapDestory(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HPDataType x);
// 堆的删除
void HeapPop(Heap* hp);
// 取堆顶的数据
HPDataType HeapTop(Heap* hp);
// 堆的数据个数
int HeapSize(Heap* hp);
// 堆的判空
int HeapEmpty(Heap* hp);
void PrintTopK(int* a, int n, int k);

主要的几个功能就是（按我的代码顺序）

---

打印（为了方便调试看结果的没什么含金量，大家自己就能完成）

//打印
void HeapPrint(Heap* hp)
{
	assert(hp);
	for (int i=0;isize;i++)
	{
		printf("%d ", hp->a[i]);
	}
	printf("\n");
}

---

堆的初始化（指针a开不开空间都可以）

//初始化
void HeapInit(Heap* hp)
{
	assert(hp);
	hp->a = NULL;
	hp->capacity = hp->size = 0;
}

---

堆的构建：给你一个杂乱的数组，把他变成堆的形式（以大堆为例）

首先肯定是把所给数组中的数据都拷贝到结构体变量hp的指针a指向的数组里面啊

由于我们在初始化指针a的时候是没有开空间的（开不开都行，我写的是没开的版本，开了的话要先考虑扩容问题）

想到memcpy

拷贝好之后就要考虑是不是符合我大堆的定义

也就是考虑

 这三个子树是不是符合父节点比子节点大的要求，可以向下调整的方法，把父节点下标传给一个向下调整的函数作为家长节点下标，把容量和指针他也传过去

向下调整函数

AdjustDown(HPDataType* a, int n, int parent)
{
	assert(a);
	int child = 2 * parent + 1;//假设是左孩子，并且左孩子是最大的孩子
	while (child 
	{
		if (child+11] > a[child] )
		{
			child = child + 1;
		}
		//此时的child已经是最大的孩子
		if (a[parent] < a[child])
		{
			Swap(&a[parent], &a[child]);
			parent=child;
			child= 2 * parent + 1;
		}
		else
		{
			break;
		}
	}
}

其中还复用了一个交换值的函数，由于后面交换的地方较多，最好还是交给函数去做

//交换
void Swap(HPDataType* a, HPDataType* b)
{
	HPDataType tmp = *a;
	*a = *b;
	*b = tmp;
}

我们发现我标记的1 2 3其实是连续的下标！！ 

所以堆创建函数

// 堆的构建
void HeapCreate(Heap* hp, HPDataType* a, int n)
{
	assert(hp);
	hp->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
	if (hp->a == NULL)
	{
		perror("HeapCreate fail");
		exit(-1);
	}
	memcpy(hp->a, a, n*sizeof(HPDataType));
	hp->size = hp->capacity=n;
	for (int i = (n - 1 - 1) / 2; i >=0; i--)
	{
		AdjustDown(hp->a, n, i);
	}
}

---

有创建肯定要有销毁，不然会内存泄漏

// 堆的销毁
void HeapDestory(Heap* hp)
{
	assert(hp);
	free(hp->a);
	hp->a = NULL;
	hp->capacity = hp->size = 0;
}

---

判断是不是空堆

// 堆的判空
int HeapEmpty(Heap* hp)
{
	assert(hp);
	return hp->size == 0;
}

---

堆的插入（尾插）

把一个接点放进去还要考虑这个节点可能会比他的父节点还大，所以他就要开始篡改族谱了...

和爸爸，爷爷...都比较一下，谁更大谁就在在上面，所以要一个函数：向上调整（还是以大堆为例）

//向上调整,大堆
void AdjustUp(HPDataType* a, int child)
{
	assert(a);
	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;
		}
	}
}

 所以堆插就是

// 堆的插入,尾插
void HeapPush(Heap* hp, HPDataType x)
{
	assert(hp);
	if (hp->capacity == hp->size)
	{
		//需要扩容
		int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
		HPDataType* newnode = (HPDataType*)realloc(hp->a,sizeof(HPDataType) * newcapacity);
		if (newnode == NULL)
		{
			perror("malloc fail");
			exit(-1);
		}
		hp->a = newnode;
		hp->capacity = newcapacity;
		
	}
        hp->a[hp->size] = x;
		hp->size++;
		//向上调整
		AdjustUp(hp->a, hp->size - 1);
}

---

堆的删除

不能简单覆盖，这样你千辛万苦的父子关系全乱套了

所以先把最后一个节点和根换一下，然后尾删直接把size--

之后就该考虑一下向下调整的问题

// 堆的删除
void HeapPop(Heap* hp)
{
	assert(hp);
	assert(!HeapEmpty(hp));
	Swap(&hp->a[0], &hp->a[hp->size - 1]);
	hp->size--;
	AdjustDown(hp->a, hp->size, 0);
}

---

取堆顶的数据

// 取堆顶的数据
HPDataType HeapTop(Heap* hp)
{
	assert(hp);
	return hp->a[0];
}

---

堆数据个数

// 堆的数据个数
int HeapSize(Heap* hp)
{
	assert(hp);
	return hp->size;
}

---

找出前k个最大 

//找出前k个最大
void PrintTopK(int* a, int n, int k)
{
	assert(a);
	Heap hp;
	while (k--)
	{
		HeapCreate(&hp, a, k);
	}
}

---

最后最后完整的实现在下面

include "Heap.h"
 
//打印
void HeapPrint(Heap* hp)
{
	assert(hp);
	for (int i=0;isize;i++)
	{
		printf("%d ", hp->a[i]);
	}
	printf("\n");
}
//交换
void Swap(HPDataType* a, HPDataType* b)
{
	HPDataType tmp = *a;
	*a = *b;
	*b = tmp;
}
 
// 堆的判空
int HeapEmpty(Heap* hp)
{
	assert(hp);
	return hp->size == 0;
}
 
// 堆的构建
void HeapCreate(Heap* hp, HPDataType* a, int n)
{
	assert(hp);
	hp->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
	if (hp->a == NULL)
	{
		perror("HeapCreate fail");
		exit(-1);
	}
	memcpy(hp->a, a, n*sizeof(HPDataType));
	hp->size = hp->capacity=n;
	for (int i = (n - 1 - 1) / 2; i >=0; i--)
	{
		AdjustDown(hp->a, n, i);
	}
}
//初始化
void HeapInit(Heap* hp)
{
	assert(hp);
	hp->a = NULL;
	hp->capacity = hp->size = 0;
}
 
// 堆的销毁
void HeapDestory(Heap* hp)
{
	assert(hp);
	free(hp->a);
	hp->a = NULL;
	hp->capacity = hp->size = 0;
}
 
//向上调整,大堆
void AdjustUp(HPDataType* a, int child)
{
	assert(a);
	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;
		}
	}
}
// 堆的插入,尾插
void HeapPush(Heap* hp, HPDataType x)
{
	assert(hp);
	if (hp->capacity == hp->size)
	{
		//需要扩容
		int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
		HPDataType* newnode = (HPDataType*)realloc(hp->a,sizeof(HPDataType) * newcapacity);
		if (newnode == NULL)
		{
			perror("malloc fail");
			exit(-1);
		}
		hp->a = newnode;
		hp->capacity = newcapacity;
		
	}
        hp->a[hp->size] = x;
		hp->size++;
		//向上调整
		AdjustUp(hp->a, hp->size - 1);
}
 
//向下调整
AdjustDown(HPDataType* a, int n, int parent)
{
	assert(a);
	int child = 2 * parent + 1;//假设是左孩子，并且左孩子是最大的孩子
	while (child 
	{
		if (child+11] > a[child] )
		{
			child = child + 1;
		}
		//此时的child已经是最大的孩子
		if (a[parent] < a[child])
		{
			Swap(&a[parent], &a[child]);
			parent=child;
			child= 2 * parent + 1;
		}
		else
		{
			break;
		}
	}
}
 
// 堆的删除
void HeapPop(Heap* hp)
{
	assert(hp);
	assert(!HeapEmpty(hp));
	Swap(&hp->a[0], &hp->a[hp->size - 1]);
	hp->size--;
	AdjustDown(hp->a, hp->size, 0);
}
// 取堆顶的数据
HPDataType HeapTop(Heap* hp)
{
	assert(hp);
	return hp->a[0];
}
// 堆的数据个数
int HeapSize(Heap* hp)
{
	assert(hp);
	return hp->size;
}
//找出前k个最大
void PrintTopK(int* a, int n, int k)
{
	assert(a);
	Heap hp;
	while (k--)
	{
		HeapCreate(&hp, a, k);
	}
}

---

学会了吗？？不懂的留言~