文档建议反馈控制台
首页
学习
活动
专区
圈层
工具
MCP广场
文章/答案/技术大牛
发布
社区首页 >专栏 >【数据结构初阶】二叉树--堆(顺序结构实现)

【数据结构初阶】二叉树--堆(顺序结构实现)

作者头像
云边有个稻草人
发布于 2024-10-21 20:02:51
发布于 2024-10-21 20:02:51
2310
举报
文章被收录于专栏：C++领域相关博客C++领域相关博客

一、实现顺序结构二叉树

一般堆使用顺序结构的数组来存储数据，堆是一种特殊的二叉树，分为大根堆（大堆）和小根堆（小堆），具有二叉树的特性的同时，还具备其他的特性。

1.1 堆的概念和结构

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

小堆：父结点不大于孩子结点；大堆：父结点不小于孩子结点。

数组不一定是有序地。小堆堆顶是堆的最小值，大堆堆顶是堆的最大值。

1.2 堆及二叉树的性质

堆的性质

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

二叉树的性质

  • 对于具有 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 则无右孩子；

通俗点来讲，父结点i---> 左孩子：2i+1，右孩子：2i+2。

1.3 堆的实现

1.3.1 创建堆的结构

堆的底层结构是数组

代码语言：javascript
复制
//创建堆的结构
typedef int HPDataType;
typedef struct Heap
{
	HPDataType* arr;
	int size;//堆中有效数据的个数
	int capacity;//堆的容量
}HP;
1.3.2 初始化和销毁
代码语言：javascript
复制
//初始化
void HPInit(HP* php)
{
	assert(php);
	php->arr = NULL;
	php->size = php->capacity = 0;
}

//销毁
void HPDestroy(HP* php)
{
	assert(php);

	 if(php->arr)
	{
		free(php->arr);
		php->arr = NULL;
	}

	php->size = php->capacity = 0;

}
1.3.3 入堆+向上调整算法（创建一个小堆）

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

向上调整算法

  • 先将元素插入到堆的末尾，即最后一个子结点之后；
  • 插入之后如果堆的性质遭到破坏，将新插入结点顺着双亲结点往上调整到合适位置即可。

【举例，向上调整算法】

思路：新插入的数据作为子结点（child），找到新插入数据的父结点（parent=（child-1）/ 2）（上面二叉树的性质），父结点和子结点进行比较，若父结点大于子结点，数据交换，不大于则不交换。再找新的父结点和子结点，循环条件是 child>0，child不需要等于0，child等于0时为根结点，根结点没有父结点不需要发生交换。

代码语言：javascript
复制
void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}

//向上调整算法
void AdjustUp(HPDataType* arr, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (arr[child] < arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

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

	//判断空间是否充足
	if (php->size == php->capacity)
	{
		int newCapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
		HPDataType* tmp = (HPDataType*)realloc(php->arr, newCapacity * sizeof(HPDataType));
		if (tmp == NULL)
		{
			perror("realloc file!");
			exit(1);
		}
		php->arr = tmp;
		php->capacity = newCapacity;
	}
	//此时空间已经充足
    //我们应该清楚地知道，size是x的下标，size在数组中指向x这个元素
	php->arr[php->size] = x;

	//向上调整算法
	AdjustUp(php->arr, php->size);

	php->size++;
}
1.3.4 出堆+向下调整算法（小堆）

堆的删除（出堆）

删除堆是删除堆顶的数据，将堆顶的数据跟最后一个数据进行交换，然后删除数组最后一个数据，再进行向下调整算法。

向下调整算法有一个前提：左右子树必须是一个堆，才能进行调整。

出堆

  • 将堆顶元素与堆中最后一个元素进行交换；
  • 删除堆中最后一个元素；
  • 将堆顶元素向下调整到满足堆特性为止。

【向下调整算法】

思路：堆顶元素为父结点，找到左右孩子中最小的那个子结点与之比较，若父结点大于子结点，交换，不大于则不交换，不断找新的父结点和子结点，就这样循环，注意循环结束的条件。上代码，结合代码中的注释更好的理解。

代码语言：javascript
复制
//向下调整算法
void AdjustDown(HPDataType* arr, int parent, int n)
{
	int child = parent * 2 + 1;//左孩子
	while (child < n)
	{
		//找左右孩子中最小的
        //child + 1 < n , 保证不越界
		if (child + 1 < n && arr[child] > arr[child + 1])
		{
			child++;
		}
		if (arr[parent] > arr[child])
		{
			Swap(&arr[child], &arr[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

//出堆
void HPPop(HP* php)
{
	assert(php && php->size);
    
	Swap(&php->arr[0], &php->arr[php->size-1]);
	php->size--;//删除掉最后一个数据(堆顶元素)

	//向下调整算法
	AdjustDown(php->arr, 0, php->size);

}
1.3.5 判空+取堆顶数据+堆中有效数据个数
代码语言：javascript
复制
//判空
bool HPEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}

//取堆顶数据
HPDataType HPTop(HP* php)
{
	assert(php && php->size);

	return php->arr[0];
}

//堆中有效数据的个数
int HPSize(HP* php)
{
	assert(php);
	return php->size;
}

二、顺序结构二叉树---源码

Heap.h

代码语言：javascript
复制
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>

//创建堆的结构
typedef int HPDataType;
typedef struct Heap
{
	HPDataType* arr;
	int size;//堆中有效数据个数
	int capacity;//堆的容量
}HP;

//初始化
void HPInit(HP* php);

//销毁
void HPDestroy(HP* php);

//入堆
void HPPush(HP* php, HPDataType x);

//出堆
void HPPop(HP* php);

//判空
bool HPEmpty(HP* php);

//取堆顶数据
HPDataType HPTop(HP* php);

//堆中有效数据的个数
int HPSize(HP* php);

Heap.c

代码语言：javascript
复制
#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"

//初始化
void HPInit(HP* php)
{
	assert(php);
	php->arr = NULL;
	php->size = php->capacity = 0;
}

//销毁
void HPDestroy(HP* php)
{
	assert(php);
	if (php->arr)
	{
		free(php->arr);
		php->arr = NULL;
	}
}

void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}

//向上调整算法
void AdjustUp(HPDataType* arr, int child)
{
	int parent = (child - 1) / 2;

	while (child > 0)//不需要等于0，child等于0时为根结点，根结点没有父结点不需要发生交换
	{
		if (arr[child] < arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

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

	//判断空间是否充足
	if (php->size == php->capacity)
	{
		int newCapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
		HPDataType* tmp = (HPDataType*)realloc(php->arr, newCapacity * sizeof(HPDataType));
		if (tmp == NULL)
		{
			perror("realloc file!");
			exit(1);
		}
		php->arr = tmp;
		php->capacity = newCapacity;
	}

	//此时空间已经充足
	php->arr[php->size] = x;

	//向上调整算法
	AdjustUp(php->arr, php->size);

	php->size++;

}

//向下调整算法
void AdjustDown(HPDataType* arr, int parent, int n)
{
	int child = parent * 2 + 1;//左孩子
	while (child < n)
	{
		//找左右孩子中最小的
		if (child + 1 < n && arr[child] > arr[child + 1])
		{
			child++;
		}
		if (arr[parent] > arr[child])
		{
			Swap(&arr[child], &arr[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

//出堆
void HPPop(HP* php)
{
	assert(php && php->size);

	Swap(&php->arr[0], &php->arr[php->size-1]);
	php->size--;

	//向下调整算法
	AdjustDown(php->arr, 0, php->size);

}

//判空
bool HPEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}

//取堆顶数据
HPDataType HPTop(HP* php)
{
	assert(php && php->size);

	return php->arr[0];
}

//堆中有效数据的个数
int HPSize(HP* php)
{
	assert(php);
	return php->size;
}

test.c

代码语言：javascript
复制
#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"

void test01()
{
	HP hp;
	HPInit(&hp);

	int arr[] = { 1,3,5,7,4,10,8 };

	for (int i = 0; i < 7; i++)
	{
		HPPush(&hp, arr[i]);
	}

	printf("堆中有效数据个数：%d\n", HPSize(&hp));

	while (!HPEmpty(&hp))
	{
		printf("%d ", HPTop(&hp));
		HPPop(&hp);
	}



	HPDestroy(&hp);


}

int main()
{

	test01();
	return 0;
}
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2024-09-01，如有侵权请联系 cloudcommunity@tencent.com 删除
算法
php
二叉树
数据结构
数据

本文分享自 作者个人站点/博客 前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ，欢迎热爱写作的你一起参与！

算法
php
二叉树
数据结构
数据
评论
登录后参与评论
0 条评论
热度
最新
登录 后参与评论
推荐阅读
目录
  • 一、实现顺序结构二叉树
    • 1.1 堆的概念和结构
    • 1.2 堆及二叉树的性质
    • 1.3 堆的实现
      • 1.3.1 创建堆的结构
      • 1.3.2 初始化和销毁
      • 1.3.3 入堆+向上调整算法（创建一个小堆）
      • 1.3.4 出堆+向下调整算法（小堆）
      • 1.3.5 判空+取堆顶数据+堆中有效数据个数
  • 二、顺序结构二叉树---源码
    • Heap.h
    • Heap.c
    • test.c
领券

腾讯云开发者

扫码关注腾讯云开发者

扫码关注腾讯云开发者

领取腾讯云代金券

热门产品

热门推荐

更多推荐

Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有 

深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 粤公网安备44030502008569号

腾讯云计算（北京）有限责任公司 京ICP证150476号 |  京ICP备11018762号

问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档

Copyright © 2013 - 2026 Tencent Cloud.

All Rights Reserved. 腾讯云 版权所有

登录 后参与评论