【数据结构】二叉树---堆

YoungMLet

发布于 2024-03-01 10:27:49

990

发布于 2024-03-01 10:27:49

文章被收录于专栏：C++/Linux

一、树的概念及结构

1. 树的概念

树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。有一个特殊的结点，称为根结点，根节点没有前驱结点。除根节点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继。因此，树是递归定义的。

2.树的相关概念

节点的度：一个节点含有的子树的个数称为该节点的度；如上图：A的为6. 叶节点或终端节点：度为0的节点称为叶节点；如上图：B、C、H、I…等节点为叶节点 非终端节点或分支节点：度不为0的节点；如上图：D、E、F、G…等节点为分支节点 双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；如上图：A是B的父节点 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；如上图：B是A的孩子节点 兄弟节点：具有相同父节点的节点互称为兄弟节点；如上图：B、C是兄弟节点 树的高度或深度：树中节点的最大层次；如上图：树的高度为4 节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙

3.树的表示

树结构相对线性表就比较复杂了，要存储表示起来就比较麻烦了，既然保存值域，也要保存结点和结点之间的关系，实际中树有很多种表示方式如：双亲表示法，孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的孩子兄弟表示法。

		typedef int DataType;
		struct Node
		{
		 	struct Node* _firstChild1; // 第一个孩子结点
		 	struct Node* _pNextBrother; // 指向其下一个兄弟结点
		 	DataType _data; // 结点中的数据域
		};

这个表示法是每次都找左边的第一个孩子，让孩子的兄弟指针去找其他的兄弟节点。

二、二叉树

1.二叉树的概念

一棵二叉树是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。

从上图可以看出：

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

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

2.特殊的二叉树

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

3.二叉树的性质

若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有 2^(i-1) 个结点.
若规定根节点的层数为1，则深度为h的二叉树的最大结点数是 2^h - 1（总结点数）.
对任何一棵二叉树, 如果度为0其叶结点个数为 n0 , 度为2的分支结点个数为 n2 ,则有 n0 ＝ n2＋1.
若规定根节点的层数为1，具有N个结点的满二叉树的深度，h= log(N+1). (ps：是log以2为底，n+1为对数)
对于具有n个结点的完全二叉树，如果按照从上至下从左至右的数组顺序对所有节点从0开始编号，则对于序号为 i 的结点有：

(1). 若i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点. (2). 若2i+1<n，左孩子序号：2i+1，2i+1>=n否则无左孩子. (3). 若2i+2<n，右孩子序号：2i+2，2i+2>=n否则无右孩子.

三、堆

1.堆的概念及结构

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

堆的性质：

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

例如小堆，在以10为父节点的子树中，它的孩子15和56都比它大；在以15为父节点的子树中，它的孩子25和30都比它大；另外，我们可以将堆的物理结构看作一个数组，实现堆的时候我们用数组模拟实现，但控制的其实是堆；

2.堆的实现

在用数组实现堆之前，我们应该知道两个性质：

知道父亲的下标 i ，我们可以求出它的左边第一个孩子的下标：i * 2 + 1；而右边的孩子下标为：i * 2 + 2；
知道孩子的下标 i ，我们可以求出它的父亲的下标：(i - 1) / 2；

（1）函数的声明

		typedef int HPDataType;
		
		typedef struct Heap
		{
			HPDataType* a;
			int size;
			int capacity;
		}HP;
		
		//向上调整---调大堆
		void AdjustUP(HPDataType* a, int child);
		
		//向下调整---调大堆
		void AdjustDown(HPDataType* a, int len, int parent);
		
		//向上/向下调整中交换
		void Swap(HPDataType* p1, HPDataType* p2);
		
		
		//初始化
		void HeapInit(HP* php);
		
		//入堆
		void HeapPush(HP* php, HPDataType x);
		
		//删除堆顶的数据
		void HeapPop(HP* php);
		
		//获取堆顶元素
		HPDataType HeapTop(HP* php);
		
		//获取数组模拟实现的堆的长度
		int HeapSize(HP* php);
		
		
		//判断空堆
		bool HeapEmpty(HP* php);
		
		//释放内存
		void HeapDestory(HP* php);

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

堆向上调整算法：从一个节点开始往上开始调整，这个节点一般是叶子，如果调的是大堆，那么就是如果这个节点的父亲比它小，那么就将这两个节点交换；堆向上调整算法的前提是：开始调整的节点上面必须是一个大/小堆；

下面看代码的具体实现：

（2）函数的实现

		//初始化
		void HeapInit(HP* php)
		{
			assert(php);
		
			php->a = NULL;
			php->size = 0;
			php->capacity = 0;
		}
		
		
		//判断空堆
		bool HeapEmpty(HP* php)
		{
			assert(php);
		
			return php->size == 0;
		}
		
		
		
		//向上/向下调整中交换
		void Swap(HPDataType* p1, HPDataType* p2)
		{
			HPDataType tmp = *p1;
			*p1 = *p2;
			*p2 = tmp;
		}

向上调整算法，它的最坏情况是向上调整高度次，一颗完全二叉树的高度是 logN ，所以它的时间复杂度是 O(logN)；

		//向上调整---调大堆
		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;
				}
			}
		}

向下调整算法，它的最坏情况也是向下调整高度次，一颗完全二叉树的高度是 logN ，所以它的时间复杂度也是 O(logN)；

		//向下调整---调大堆
		void AdjustDown(HPDataType* a, int len, int parent)
		{
			//先定义孩子的节点是父节点的左边第一个
			int child = parent * 2 + 1;
		
			while (child < len)
			{
				//找出孩子节点中较大的那个
				if (child + 1 < len && 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 HeapPush(HP* php, HPDataType x)
		{
			assert(php);
		
			//扩容
			if (php->size == php->capacity)
			{
				int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
				HPDataType* newphp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);
				assert(newphp);
		
				php->a = newphp;
				php->capacity = newcapacity;
			}
		
			php->a[php->size] = x;
			php->size++;
		
			//向上调整
			AdjustUP(php->a, php->size - 1);
			
		}
		
		
		//删除堆顶的数据
		void HeapPop(HP* php)
		{
			assert(php);
			assert(!HeapEmpty(php));
		
			Swap(&php->a[0], &php->a[php->size - 1]);
			php->size--;
		
			AdjustDown(php->a, php->size, 0);
		}
		
		
		//获取堆顶元素
		HPDataType HeapTop(HP* php)
		{
			assert(php);
			assert(!HeapEmpty(php));
		
			return php->a[0];
		}
		
		
		//获取数组模拟实现的堆的长度
		int HeapSize(HP* php)
		{
			assert(php);
		
			return php->size;
		}
		
		
		//释放内存
		void HeapDestory(HP* php)
		{
			free(php->a);
			php->a = NULL;
			php->capacity = 0;
			php->size = 0;
		}

（3）测试堆的基本操作

		void TestHeap()
		{
			HP hp;
			HeapInit(&hp);
		
			int a[] = { 65,100,70,32,50,60 };
			for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
			{
				HeapPush(&hp, a[i]);
			}
		
			while (!HeapEmpty(&hp))
			{
				int top = HeapTop(&hp);
				printf("%d\n", top);
				HeapPop(&hp);
			}
		
			HeapDestory(&hp);
		}

测试结果如下：

3.堆的应用

（1）堆排序

堆排序的思路是，首先要建立一个堆，如果是排升序，就建大堆，因为大堆中，大的在前面，每次让堆顶的数据与堆尾的数据的值进行交换，交换完长度减一，相当于最大的放到后面就不动了，然后再从堆顶开始向下调整，次大的调到堆顶，然后和倒数第二的数据的值进行交换…直到长度减到0.

这里建堆推荐使用向下建堆，因为向下建堆的时间复杂度为 O(N) ，而向上建堆的时间复杂度为 O(N * logN) ；

		//堆排
		void HeapSort(int* a, int len)
		{
		
			//向上建堆---大堆（时间复杂度:O(N * logN)）
			/*for (int i = 1; i < len; i++)
			{
				AdjustUP(a, i);
			}*/
		
			//向下建堆---大堆（时间复杂度:O(N)）
			for (int i = (len - 1 - 1) / 2; i >= 0; i--)
			{
				AdjustDown(a, len, i);
			}
		
			//每次交换第一个与最后一个的数据，交换完数据长度 -1 ，从下标 0 开始向下调整
			while (len)
			{
				Swap(&a[0], &a[len - 1]);
				len--;
				AdjustDown(a, len, 0);
			}
		}

其中实现的结果如下：

（2）TopK

TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。

对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：

用数据集合中前K个元素来建堆前k个最大的元素，则建小堆前k个最小的元素，则建大堆
用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素，将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。

先生成数据，这里只生成 100000 以内的数据，方便后面进行检验；

		void CreateNDate()
		{
			// 造数据，1000个
			int n = 1000;
			srand(time(0));
		
			//创建文档
			const char* file = "data.txt";
		
			//以write的方式打开文档
			FILE* fin = fopen(file, "w");
			assert(fin);
		
			//生成 100000 以内的随机数写入文档中
			for (size_t i = 0; i < n; ++i)
			{
				int x = rand() % 100000;
				fprintf(fin, "%d\n", x);
			}
		
			//关闭文档
			fclose(fin);
		}

寻找前 k 个最大的数据；

		void PrintTopK(int k)
		{
			//创建文档，已存在就忽略
			const char* file = "data.txt";
		
			//以只读的方式打开
			FILE* fout = fopen(file, "r");
			assert(fout);
		
			//开辟 k 个空间，即前 k 个数据的空间
			int* kminheap = (int*)malloc(sizeof(int) * k);
			assert(kminheap);
		
			//从文档中读取前 k 个数据，放入kminheap数组中
			for (int i = 0; i < k; i++)
			{
				fscanf(fout, "%d", &kminheap[i]);
			}
		
			// 建小堆
			for (int i = (k - 1 - 1) / 2; i >= 0; i--)
			{
				AdjustDown(kminheap, k, i);
			}
		
			// 继续读取文档中 N - K 个数据
			//如果读取到比堆顶大的数据，就直接覆盖堆顶的数据，然后向下调整
			//直到读取文档中的数据失败，即读取完全部数据
			int val = 0;
			while (!feof(fout))
			{
				fscanf(fout, "%d", &val);
				if (val > kminheap[0])
				{
					kminheap[0] = val;
					AdjustDown(kminheap, k, 0);
				}
			}
		
			//打印前 k 个
			for (int i = 0; i < k; i++)
			{
				printf("%d ", kminheap[i]);
			}
			printf("\n");
		}

这里上面只生成了 100000 以内的数据，所以我们手动改变文档中的值，随机将 5 个值的后面加上四个 4 ，即变成了最大的五个数，如下图，证明了我们的代码是正确的；