【数据结构】树-堆的详解

目录

1.树的概念

树的相关概念：

结点的度：

叶结点或终端结点：

非终端结点或分支结点：

双亲结点或父结点：

孩子结点或子结点：

兄弟结点：

树的度：

结点的层次：

树的高度或深度：

堂兄弟结点：

结点的祖先：

子孙：

森林：

二叉树的概念

堆的概念

大堆，小堆概念 

 堆的实现

堆的底层逻辑：动态数组 

初始化和销毁 

堆的插入 

堆的删除 

堆的判空和取堆的顶数据

整体代码及测试： 

 

---

1.树的概念

在学习了解堆之前，我们需要来了解树，堆是树中的一种特殊情况。 

可能我们听到树这个名字时，脑海中就会不由自主的浮现一颗树的形状，树作为数据结构的一环，它的，模型就像是一颗倒着的树一样的结构，每个节点存放着我们需要的数据，示例图如下：

树的相关概念：

结点的度：

如图所示，节点的度指的就是该节点所连接的其他节点个数，图中A节点的度为6，B节点的度为3 

叶结点或终端结点：

 叶结点或终端结点又称作叶子，就像一颗树上的叶子一样，后续没有枝干延升了，树中的叶子节点指的就是那些度为0的节点。

非终端结点或分支结点：

指的就是那些度不为0的节点

双亲结点或父结点：

如图，A为父亲的话，那么B,C,D,E,F,G都是它的孩子

孩子结点或子结点：

指的就是B,C,D,E,F,G

兄弟结点：

树的度：

以树中节点度中的最大一个为树的度，如图树中A节点的度最大为6，那么树的度就是为6

结点的层次：

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

树的高度或深度：

 树中结点的最大层次； 如上图：树的高度为4

堂兄弟结点：

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

结点的祖先：

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

子孙：

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

森林：

由m（m>0）棵互不相交的树的集合称为森林
 

二叉树的概念

 二叉树是树中特殊的一种，它的每一个父亲节点的孩子都不会超过两个。

•  二叉树不存在度大于2的结点
• 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

以下又是二叉树的各种情况： 

 

• 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是 ，则它就是满二叉树。
• 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。

堆的概念

堆就属于满二叉树或者完全二叉树的一种，堆的底层实现可以通过顺序存储或者链式存储，本次我们实现的是顺序存储。那么一个堆在底层的顺序存储又是什么样子的呢，看下图。

 通过上图我们又可以了解如何使用每一个父亲节点去计算孩子节点：

• 左child = parent * 2 + 1  
• 右child = parent * 2 + 2

 通过孩子计算父亲节点：

• parent = (child - 1) /2

大堆，小堆概念 

• 大堆：所有的父亲节点的数据都>=孩子节点
• 小堆：所有的父亲节点的数据都<=孩子节点 

 堆的实现

堆的底层逻辑：动态数组 

#include <stdio.h>
#include <assert.h>
#include <stdbool.h>
#include <stdlib.h>
 
// 类型定义
typedef int HPDataTpye;
 
typedef struct Heap
{
	// 动态数组
	HPDataTpye* a;
	// 元素个数
	int size;
	// 空间容量
	int capacity;
}Heap;

其实操作堆的底层就是对动态数组的操作，我们只需按照堆的方式进行设计即可。 

以下是我们会实现的接口功能： 

// 函数声明
 
// 堆的初始化
void HeapInit(Heap* php);
 
// 堆的销毁
void HeapDestory(Heap* php);
 
// 堆的插入
void HeapPush(Heap* php, HPDataTpye x);
 
// 堆的删除
void HeapPop(Heap* php);
 
// 堆的判空
bool HeapEmpty(Heap* php);
 
// 取堆的顶数据
HPDataTpye HeapTop(Heap* php);

初始化和销毁 

// 堆的初始化
void HeapInit(Heap* php)
{
	// 判空
	assert(php);
 
	// 初始化
	php->a = NULL;
	php->size = php->capacity = 0;
 
}
 
// 堆的销毁
void HeapDestory(Heap* php)
{
	// 判空
	assert(php);
 
	// 释放空间
	free(php->a);
	php->a = NULL;
	php->size = php->capacity = 0;
 
}

堆的插入 

 这边我们先实现一个大堆的案例：

首先我们在插入堆的情况可能有以下三种情况： 

 

 

如果插入的数据是图一的情况，我们直接不用管理了，插入之后还是一个大堆，但是如果是图二或者图三的情况，我们就需要对堆进行一个调整，将它调整为大堆的情况。

首先我们需要计算出最后插入数据的父亲节点，让后进行比较，如果刚插入的孩子节点大我们就进行交换，简单点说就是谁大谁当爹，然后通过这样不断的调整，直到插入的孩子到顶，或者中途有父亲节点比它大才结束。

以下是图形过程：

代码实现： 

// 向上调整
void AdjustUp(HPDataTpye* 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;
		}
	}
}
 
// 堆的插入
void HeapPush(Heap* php, HPDataTpye x)
{
	// 判空
	assert(php);
 
	// 判断空间是否满
	if (php->size == php->capacity)
	{
		// 看原来的空间容量是否为0，为0分配4个空间，不为0空间*2
		int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		// 分配动态空间
		HPDataTpye* tmp = (HPDataTpye*)realloc(php->a, newcapacity * sizeof(HPDataTpye));
		if (NULL == tmp)
		{
			perror("malloc fail");
			return;
		}
 
		php->a = tmp;
		php->capacity = newcapacity;
	}
 
	// 插入
	php->a[php->size - 1] = x;
	php->size++;
 
	// 向上调整
	AdjustUp(php->a, php->size-1);
}

 测试一下：

void HeapText01()
{
	Heap h;
	// 初始化
	HeapInit(&h);
 
	int arr[] = { 4,2,8,1,5,6,9,7};
	for (int i = 0; i < sizeof(arr) / sizeof(int); i++)
	{
		HeapPush(&h, arr[i]);
	}
 
	// 销毁
	HeapDestory(&h);
}
 
 
int main()
{
	HeapText01();
	return 0;
}

 

那么实现小堆模型呢，其实很简单，我们只需要将判定大小的条件改一下即可 

// 向上调整
void AdjustUp(HPDataTpye* 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;
		}
	}
}

堆的删除 

 

// 向下调整
void AdjustDown(HPDataTpye* 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[child] > a[parent])
		{
			// 交换
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else {
			break;
		}
	}
}
 
// 堆的删除
void HeapPop(Heap* php)
{
	// 判空
	assert(php);
	assert(php->size > 0);
 
	// 交换
	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;
 
	// 向下调整
	AdjustDown(php->a, php->size, 0);
}

堆的判空和取堆的顶数据

// 堆的判空
bool HeapEmpty(Heap* php)
{
	// 判空
	assert(php);
	
	return php->size == 0;
}
 
// 取堆的顶数据
HPDataTpye HeapTop(Heap* php)
{
	// 判空
	assert(php);
 
	return php->a[0];
}

时间复杂度计算 

以下图片是向上调整和向下调整的时间复杂度计算：

 

整体代码及测试： 

#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdbool.h>
#include <stdlib.h>
 
// 类型定义
typedef int HPDataTpye;
 
typedef struct Heap
{
	// 动态数组
	HPDataTpye* a;
	// 元素个数
	int size;
	// 空间容量
	int capacity;
}Heap;
 
 
// 函数声明
 
// 堆的初始化
void HeapInit(Heap* php);
 
// 堆的销毁
void HeapDestory(Heap* php);
 
// 堆的插入
void HeapPush(Heap* php, HPDataTpye x);
 
// 堆的删除
void HeapPop(Heap* php);
 
// 堆的判空
bool HeapEmpty(Heap* php);
 
// 取堆的顶数据
HPDataTpye HeapTop(Heap* php);

#include "Heap.h"
 
 
// 堆的初始化
void HeapInit(Heap* php)
{
	// 判空
	assert(php);
 
	// 初始化
	php->a = NULL;
	php->size = php->capacity = 0;
 
}
 
// 堆的销毁
void HeapDestory(Heap* php)
{
	// 判空
	assert(php);
 
	// 释放空间
	free(php->a);
	php->a = NULL;
	php->size = php->capacity = 0;
 
}
 
// 交换
void Swap(HPDataTpye* p1, HPDataTpye* p2)
{
	HPDataTpye tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
 
// 向上调整
void AdjustUp(HPDataTpye* 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;
		}
	}
}
 
// 堆的插入
void HeapPush(Heap* php, HPDataTpye x)
{
	// 判空
	assert(php);
 
	// 判断空间是否满
	if (php->size == php->capacity)
	{
		// 看原来的空间容量是否为0，为0分配4个空间，不为0空间*2
		int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		// 分配动态空间
		HPDataTpye* tmp = (HPDataTpye*)realloc(php->a, newcapacity * sizeof(HPDataTpye));
		if (NULL == tmp)
		{
			perror("malloc fail");
			return;
		}
 
		php->a = tmp;
		php->capacity = newcapacity;
	}
 
	// 插入
	php->a[php->size] = x;
	php->size++;
 
	// 向上调整
	AdjustUp(php->a, php->size - 1);
}
 
// 向下调整
void AdjustDown(HPDataTpye* 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[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else {
			break;
		}
	}
}
 
// 堆的删除
void HeapPop(Heap* php)
{
	// 判空
	assert(php);
	assert(php->size > 0);
 
	// 交换
	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;
 
	// 向下调整
	AdjustDown(php->a, php->size, 0);
}
 
 
// 堆的判空
bool HeapEmpty(Heap* php)
{
	// 判空
	assert(php);
	
	return php->size == 0;
}
 
// 取堆的顶数据
HPDataTpye HeapTop(Heap* php)
{
	// 判空
	assert(php);
	assert(php->size > 0);
 
	return php->a[0];
}

#include "Heap.h"
 
void HeapText()
{
	Heap h1;
	// 初始化
	HeapInit(&h1);
 
	int arr[] = { 4,2,8,1,5,6,9,7};
	for (int i = 0; i < sizeof(arr) / sizeof(int); i++)
	{
		HeapPush(&h1, arr[i]);
	}
 
	int i = 0;
	while (!HeapEmpty(&h1))
	{
		printf("%d ", HeapTop(&h1));
		//arr[i++] = HeapTop(&h1);
		HeapPop(&h1);
	}
	printf("\n");
 
	 //计算前十最富有的人
	/*int k = 0;
	scanf_s("%d", &k);
	while (k--)
	{
		printf("%d ", HeapTop(&h1));
		HeapPop(&h1);
	}*/
 
 
	// 销毁
	HeapDestory(&h1);
}
 
 
 
 
int main()
{
	HeapText();
	return 0;
}