数据结构——堆(二叉树)的结构及实现(C语言)

灰太狼 2023-01-04 11:55 142阅读 0赞

### 堆的C语言实现 ###

*  一、堆的概念及结构
 *   *  1.1 什么是堆？
     *  1.2 堆的结构
 *  二、堆的实现
 *   *  2.1 堆向下调整法
     *  2.2 堆的创建
     *  2.3 堆的销毁
     *  2.4 堆的插入
     *  2.5 堆的删除
     *  2.6 取堆顶的数据
     *  2.7 堆的数据个数
     *  2.8 堆的判空
 *  三、堆排序
 *  四、代码清单
 *   *  4.1 Heap.h
     *  4.2 Heap.c
     *  4.3 test.c

# 一、堆的概念及结构 #

## 1.1 什么是堆？ ##

> 将数组中的所有元素按照完全二叉树的顺序存储方式存储在一个一维数组中

堆具有如下性质：

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

堆可以分为两类：

>  *  **大根堆**：每个节点的值都小于父节点的值；
>  *  **小根堆**：每个节点的值都大于父节点的值；

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70]

## 1.2 堆的结构 ##

如上图所示，堆的**逻辑结构是一个完全二叉树，存储结构是一个数组**。

typedef int HPDataType;
    
    typedef struct Heap
    {
        
    	HPDataType* _a;	
    	int _size;		//堆中有效元素个数
    	int _capacity;	//堆容量
    }Heap;

# 二、堆的实现 #

了解了堆的结构后，我们就可以实现堆了，但是先找出堆中父节点与左右孩子节点的关系。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70 1]

如上图所示我们可以得到父亲节点与左右孩子节点的关系，

> **假设父节点(parent)为 i** ，则：  
>  左 孩 子 ( L C h i l d ) = 2 ∗ i + 1 右 孩 子 ( R C h i l d ) = 2 ∗ i + 2 左孩子(LChild)=2\*i+1 \\\\ 右孩子(RChild)=2\*i+2 左孩子(LChild)=2∗i\+1右孩子(RChild)=2∗i\+2

int parent = i;		//父节点
    int LChild = parent * 2 + 1;	//左孩子
    int RChild = parent *2 +1;		//右孩子

> **假设子节点(Child)为 i**，则  
>  父 节 点 ( p a r e n t ) = ( i − 1 ) 2 父节点(parent)=\\dfrac\{(i-1)\}\{2\} 父节点(parent)=2(i−1)

int child = i;		//孩子节点，左右孩子结点不用区分，因为类型为int
    int parent = (child-1)/2;	//父节点

通过上述关系，我们就可以在知道某个节点的位置后，查找其父节点和子节点了。

## 2.1 堆向下调整法 ##

在构建堆之前，我们需要掌握一个算法来将堆构建成大根堆或小根堆，我们以小根堆为例讲解，该算法有一个前提：

> **左右子树必须是一个堆(大根堆或者小根堆)，才能调整**

如下图所示，数组定义如下

int a[] = {
        27,15,19,18,28,34,65,49,25,37};

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70 2]  
如上图所示，27的左右子树均是小根堆，那么就可以通过向下调整下将该堆构建成小根堆。

> 步骤为首先以**根节点27作为parent**，然后遍历二叉树，**找出左孩子和右孩子中较小的节点作为孩子节点(child)**，当**父节点大于孩子节点时就交换数据**，直到遍历到最后一个叶子节点。

//数据交换
    void swap(HPDataType* p1, HPDataType* p2)
    {
        
    	HPDataType tmp = *p1;
    	*p1 = *p2;
    	*p2 = tmp;
    }
    
    //堆向下调整算法
    void AdjustDown(HPDataType* a, int n, int root)
    {
        
    	//1.首先确定父节点与孩子节点，默认孩子节点为左孩子
    	int parent = root;
    	int child = parent * 2 + 1;	//不区分左右孩子，默认左孩子为孩子节点	
    	//遍历二叉树，当孩子节点超出数组范围则停止
    	while (child < n)
    	{
        
    		//找出左右孩子中最小的节点作为孩子节点
    		if ((child + 1 < n) && (a[child + 1] < a[child]))
    		{
        
    			child++;
    		}
    
    		//如果父亲节点大于孩子节点则交换，否则退出循环
    		if (a[parent] > a[child])
    		{
        
    			swap(&a[parent], &a[child]);	//交换
    			parent = child;		//孩子节点作为新的父节点
    			child = 2 * parent + 1;		//默认左孩子作为新的孩子节点
    		}
    		else
    		{
        
    			break;
    		}
    	}
    
    }

## 2.2 堆的创建 ##

在掌握了向下调整算法后就可以实现堆创建了，我们从二叉树中**最后一个叶子节点开始调整**，即数组中最后一个元素，**一直调整到根节点的树**，就可以调整成堆，即遍历数组中的每一个元素。

//构建堆,从最后一个节点开始依次遍历执行向下调整算法，一直到根节点，可以找到最小的数
    for (int i = n - 1; i >= 0; --i)
    	{
        
    		AdjustDown(php->_a, n, i);
    	}

但真的需要这样操作吗？  
如下图所示，**叶子节点没有左右子树因此即可以看作大根堆也可以看作小根堆**，实际上并不需要调整，只需要**从最后一个节点的父节开始调整**，即倒数第一个非叶子节点的子树开始调整，一直到根节点的树就可以调整成堆，并选择出最小的元素作为根节点。

> 例如：下图的最后一个节点为37，对应数组下标为 i = n − 1 = 9 i = n-1= 9 i=n−1=9 ，其父节点下标为 ( i − 1 ) 2 = 9 − 1 2 = 4 \\frac\{(i-1)\}\{2\}=\\frac\{9-1\}\{2\}=4 2(i−1)=29−1=4，也就是28开始 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70 3]

//堆的创建
    void HeapInit(Heap * php, HPDataType * a, int n)
    {
        
    	assert(php);
    
    	php->_a = (HPDataType *)malloc(sizeof(HPDataType)*n);
    	//复制堆
    	memcpy(php->_a, a, sizeof(HPDataType)*n);
    	php->_size = n;
    	php->_capacity = n;
    	
    	//这种方法不够优化因此不采用
    	//for (int i = n - 1; i >= 0; --i)
    	//{
        
    	//	AdjustDown(php->_a, n, i);
    	//}
    
    	//构建堆,从最后一个节点开始依次遍历执行向下调整算法，一直到根节点，可以找到最小的数
    	for (int i = (n - 2) / 2; i >= 0; --i)
    	{
        
    		AdjustDown(php->_a, n, i);
    	}
    }

## 2.3 堆的销毁 ##

//堆的销毁
    void HeapDestory(Heap* php)
    {
        
    	free(php->_a);		//先free堆中的数组
    	php->_a = NULL;
    	php->_size = php->_capacity = 0;
    }

## 2.4 堆的插入 ##

堆的插入是将数据**插入到数组尾上**，在进行**向上调整算法**，直到满足堆。

> 向上调整算法如图所示  
> 先插入到数组末尾  
> 1.10与28比较，小于28，交换；  
> 2.10与18比较，小于18，交换；  
> 3.10与15比较，小于15，交换；  
> 4.满足堆调整完成。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70 4]

//堆的插入
    void HeapPush(Heap* php, HPDataType x)
    {
        
    	assert(php);
    
    	//堆满，重新申请空间
    	if (php->_size == php->_capacity)
    	{
        
    		php->_capacity *= 2;	//扩大2倍
    		HPDataType *tmp = (HPDataType *)realloc(php->_a, sizeof(HPDataType)*php->_capacity);
    		if (NULL == tmp)
    		{
        
    			printf("内存申请失败！\n");
    			exit(-1);
    		}
    		php->_a = tmp;
    	}
    	
    
    	php->_a[php->_size++] = x;	//元素插入数组末尾
    	AdjustUp(php->_a, php->_size, php->_size - 1);
    }

## 2.5 堆的删除 ##

删除堆是**删除堆顶**的数据，**将堆顶的数据和最后一个数据交换**，然后**删除数组最后一个数据**，再进行**向下调整算法**。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70 5]

//堆的删除
    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);
    }

## 2.6 取堆顶的数据 ##

HPDataType HeapTop(Heap* php)
    {
        
    	assert(php);
    	assert(php->_size > 0);
    
    	return php->_a[0];
    }

## 2.7 堆的数据个数 ##

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

## 2.8 堆的判空 ##

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

# 三、堆排序 #

执行堆排序的步骤为

> 首先构建堆，然后**交换堆顶与堆中最后一个节点**,然后**删除最后一个元素**，**执行向下调整算法**，直到最后一个元素  
> 小根堆：每次挑出最小的元素，**降序排序**  
> 大根堆：每次挑出最大的元素，**升序排序**  
> **注意：**  
> **每次删除最后一个元素**并不是物理结构上的删除，即**不是删除二叉树的结点**，而是**指逻辑结构上的删除便于我们理解和操作**，即只是让数组的长度减一再执行向下调整。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70 6]

//对数组进行堆排序
    void HeapSort(HPDataType *a, int n)
    {
        
    
    	//1.构建堆,从最后一个节点开始依次遍历执行向下调整算法，一直到根节点，可以找到最小的数
    	for (int i = (n - 2) / 2; i >= 0; --i)
    	{
        
    		AdjustDown(a, n, i);
    	}
    
    	//每次和最后一个元素交换执行向下调整
    	int end = n - 1;	//end为最后一个元素的数组下标
    	while(end > 0)
    	{
        
    		swap(&a[0], &a[end]);
    		AdjustDown(a, end, 0);
    		--end;
    	}
    
    	for (int i = 0; i < n; ++i)
    	{
        
    		printf("%d ", a[i]);
    	}
    	printf("\n");
    
    }

测试

int main()
    {
        
    	int a[] = {
         27,15,19,18,28,34,65,49,25,37 };
    	HeapSort(a, 10);
    	return 0;
    }

结果  
![在这里插入图片描述][20210110184752862.png]

# 四、代码清单 #

## 4.1 Heap.h ##

#pragma once
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #include<assert.h>
    
    typedef int HPDataType;
    
    typedef struct Heap
    {
        
    	HPDataType* _a;	
    	int _size;		//堆中有效元素个数
    	int _capacity;	//堆容量
    }Heap;
    
    //堆的创建
    void HeapInit(Heap * php, HPDataType * a, int n);
    
    //堆的销毁
    void HeapDestory(Heap* php);
    
    //堆的插入
    void HeapPush(Heap* php, HPDataType x);
    
    //堆的删除
    void HeapPop(Heap* php);
    
    //取堆顶的数据
    HPDataType HeapTop(Heap* php);
    
    //堆的数据个数
    int HeapSize(Heap* php);
    
    //堆的判空
    int HeapEmpty(Heap* php);
    
    //对数组进行堆排序
    void HeapSort(HPDataType *a, int n);
    
    //堆打印
    void HeapPrint(HPDataType *php, int n);

## 4.2 Heap.c ##

#include"Heap.h"
    
    //数据交换
    void swap(HPDataType* p1, HPDataType* p2)
    {
        
    	HPDataType tmp = *p1;
    	*p1 = *p2;
    	*p2 = tmp;
    }
    
    //堆向下调整算法
    void AdjustDown(HPDataType* a, int n, int root)
    {
        
    	//1.首先确定父节点与孩子节点，默认孩子节点为左孩子
    	int parent = root;
    	int child = parent * 2 + 1;	//不区分左右孩子，默认左孩子为孩子节点	
    	//遍历二叉树，当孩子节点超出数组范围则停止
    	while (child < n)
    	{
        
    		//找出左右孩子中最小的节点作为孩子节点
    		if ((child + 1 < n) && (a[child + 1] < a[child]))
    		{
        
    			child++;
    		}
    
    		//如果父亲节点大于孩子节点则交换，否则退出循环
    		if (a[parent] > a[child])
    		{
        
    			swap(&a[parent], &a[child]);	//交换
    			parent = child;		//孩子节点作为新的父节点
    			child = 2 * parent + 1;		//默认左孩子作为新的孩子节点
    		}
    		else
    		{
        
    			break;
    		}
    	}
    
    }
    
    void AdjustUp(HPDataType* a, int n, int child)
    {
        
    	int parent = (child - 1) / 2;	//新元素的父节点；
    								//向上调整直到根节点
    	while (child > 0)
    	{
        
    		//小根堆：如果父节点大于子节点就交换
    		if (a[parent] >a[child])
    		{
        
    			swap(&a[parent], &a[child]);
    			child = parent;		//父节点作为新的孩子节点
    			parent = (child - 1) / 2;	//新的孩子节点的父节点
    		}
    		else
    		{
        
    			break;
    		}
    	}
    
    
    }
    
    //堆的创建
    void HeapInit(Heap * php, HPDataType * a, int n)
    {
        
    	assert(php);
    
    	php->_a = (HPDataType *)malloc(sizeof(HPDataType)*n);
    	//复制堆
    	memcpy(php->_a, a, sizeof(HPDataType)*n);
    	php->_size = n;
    	php->_capacity = n;
    	
    	//这种方法不够优化因此不采用
    	//for (int i = n - 1; i >= 0; --i)
    	//{
        
    	//	AdjustDown(php->_a, n, i);
    	//}
    
    	//构建堆,从最后一个节点开始依次遍历执行向下调整算法，一直到根节点，可以找到最小的数
    	for (int i = (n - 2) / 2; i >= 0; --i)
    	{
        
    		AdjustDown(php->_a, n, i);
    	}
    }
    
    //堆的销毁
    void HeapDestory(Heap* php)
    {
        
    	free(php->_a);		//先free堆中的数组
    	php->_a = NULL;
    	php->_size = php->_capacity = 0;
    }
    
    //堆的插入
    void HeapPush(Heap* php, HPDataType x)
    {
        
    	assert(php);
    
    	//堆满，重新申请空间
    	if (php->_size == php->_capacity)
    	{
        
    		php->_capacity *= 2;	//扩大2倍
    		HPDataType *tmp = (HPDataType *)realloc(php->_a, sizeof(HPDataType)*php->_capacity);
    		if (NULL == tmp)
    		{
        
    			printf("内存申请失败！\n");
    			exit(-1);
    		}
    		php->_a = tmp;
    	}
    	
    
    	php->_a[php->_size++] = x;	//元素插入数组末尾
    	AdjustUp(php->_a, php->_size, php->_size - 1);
    }
    
    
    //堆的删除
    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);
    }
    
    //取堆顶的数据
    HPDataType HeapTop(Heap* php)
    {
        
    	assert(php);
    	assert(php->_size > 0);
    
    	return php->_a[0];
    }
    
    //堆的数据个数
    int HeapSize(Heap* php)
    {
        
    	assert(php);
    
    	return php->_size;
    }
    
    //堆的判空
    int HeapEmpty(Heap* php)
    {
        
    	assert(php);
    
    	return php->_size == 0;
    }
    
    
    //对数组进行堆排序
    void HeapSort(HPDataType *a, int n)
    {
        
    
    	//1.构建堆,从最后一个节点开始依次遍历执行向下调整算法，一直到根节点，可以找到最小的数
    	for (int i = (n - 2) / 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;
    	}
    
    }
    
    //堆打印
    void HeapPrint(HPDataType *a, int n)
    {
        
    	assert(a);
    	assert(n);
    	for (int i = 0; i < n; ++i)
    	{
        
    		printf("%d ", a[i]);
    	}
    	printf("\n");
    }

## 4.3 test.c ##

#include"Heap.h"
    
    void TestHeap()
    {
        
    	//int a[] = { 27,15,19,18,28,34,65,49,25,37 };
    	//
    	//HeapSort(a, sizeof(a) / sizeof(HPDataType));
    	//HeapPrint(a,sizeof(a)/sizeof(HPDataType));
    
    	int a[] = {
         27,15,19,18,28,34,65,49,25,37 };
    	Heap hp;
    	HeapInit(&hp, a, sizeof(a) / sizeof(HPDataType));
    	HeapPrint(hp._a, hp._size);
    	HeapPush(&hp, 10);
    	HeapPush(&hp, 11);
    	HeapPush(&hp, 42);
    	HeapPrint(hp._a, hp._size);
    	HeapPop(&hp);
    	//HeapPop(&hp);
    	//HeapPop(&hp);
    	//HeapPop(&hp);
    	//HeapPop(&hp);
    	//HeapPop(&hp);
    	//HeapPop(&hp);
    	//HeapPop(&hp);
    	//HeapPop(&hp);
    	//HeapPop(&hp);
    	//HeapPop(&hp);
    	//HeapPop(&hp);
    	//HeapPop(&hp);
    	HeapPrint(hp._a, hp._size);
    	printf("%d\n",HeapTop(&hp));
    	printf("%d\n", HeapSize(&hp));
    	printf("%d\n", HeapEmpty(&hp));
    	HeapDestory(&hp);
    	//printf("%d\n", HeapTop(&hp));
    	printf("%d\n", HeapSize(&hp));
    	printf("%d\n", HeapEmpty(&hp));
    
    
    
    
    
    
    }
    
    int main()
    {
        
    	TestHeap();
    
    	system("pause");
    	return 0;
    }

![在这里插入图片描述][20210110205050715.png]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70]: /images/20221119/0fc5d479fe9341cebd48741c9060c2e0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70 1]: /images/20221119/39c89054d5b848218c06b769906e7fb5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70 2]: /images/20221119/2c7e688dc66340c4a00bc3600b3a892e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70 3]: /images/20221119/f3d195f3e87b4540bed3505d604cf33f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70 4]: /images/20221119/dda9fa11ffef44b9bd6fbb9a5984979e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70 5]: /images/20221119/70a1df1417b547988b869df4ea9b898d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMDc2MDIy_size_16_color_FFFFFF_t_70 6]: /images/20221119/d5afb48ee6c44d71bb5f80ef7c87ab29.png
[20210110184752862.png]: /images/20221119/cbbdbc50f9094734a153b49486746c04.png
[20210110205050715.png]: /images/20221119/f444adb020b9402587d941bad379f3f6.png