手机移动端网站,网站用的什么字体,北京百度推广排名优化,wordpress文章伪静态【数据结构入门指南】二叉树顺序结构: 堆及实现#xff08;全程配图#xff0c;非常经典#xff09; 一、前言#xff1a;二叉树的顺序结构二、堆的概念及结构三、堆的实现#xff08;本篇博客以实现小堆为例#xff09;3.1 准备工作3.2 初始化3.3 堆的插入3.3.1 向上调… 【数据结构入门指南】二叉树顺序结构: 堆及实现全程配图非常经典 一、前言二叉树的顺序结构二、堆的概念及结构三、堆的实现本篇博客以实现小堆为例3.1 准备工作3.2 初始化3.3 堆的插入3.3.1 向上调整算法 3.4 堆的删除3.4.1 向下调整算法 3.5 堆的判空font colororange接下的过于简单直接给出带啊吗3.6 取堆顶的数据3.7 堆的个数3.8 堆的销毁 四、所有代码 一、前言二叉树的顺序结构 普通的二叉树是不适合用数组来存储的因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。 现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事一个是数据结构一个是操作系统中管理内存的一块区域分段。 二、堆的概念及结构 堆是一种特殊的数据结构,可以将堆分为大顶堆和小顶堆两种形式。堆中的每个节点都有一个值并且满足以下两个条件 ①堆的父节点的值总是大于或等于其子节点的值大顶堆或者小于或等于其子节点的值小顶堆。 ②堆是完全二叉树即除了最底层外其他层的节点都是满的并且最底层的节点都尽量靠左排列。 大(小)堆示意图 三、堆的实现本篇博客以实现小堆为例
3.1 准备工作 由于堆是通过数组来实现的所以我们也和顺序表一样首先要创建一个结构体来存储数组指针 容量 存储数据大小。 代码实现
typedef int HPDataType;
typedef struct Heap
{HPDataType* a;//数组指针int size;//存储数据大小int capacity;//容量
}HP;3.2 初始化 初始化有两种方式 ①:初始化时为数组开辟一定大小空间。②直接将数组指针置为NULL插入数据过程中在进一步处理。本篇博客采用第二种 代码实现
void HPInit(HP* php)
{assert(php);php-a NULL;php-capacity 0;php-size 0;
}3.3 堆的插入 【代码思路】 ①在插入数据前我们首先要判断是否要扩容的问题。由于前面初始化时我们直接置空所以我们先判断容量是否为空。如果为空开4个空间否则空间扩大到原来的2倍。为空时第一次具体开辟多少空间读者可自行选择本篇博客开4 ②接下来就是插入数据了但有一个问题直接插入数据可能会破坏堆的结构所以我们采用了向上调整算法。 代码
void HPPush(HP* php, HPDataType x)
{assert(php);//扩容if (php-size php-capacity){int newcapacity php-size 0 ? 4 : php-capacity * 2;HPDataType* tmp (HPDataType*)realloc(php-a,sizeof(HPDataType) * newcapacity);if (tmp NULL){perror(malloc fail);exit(-1);}php-a tmp;php-capacity newcapacity;}//插入数据php-a[php-size] x;php-size;//向上调整AdjustUp(php-a, php-size - 1);
}3.3.1 向上调整算法 【代码思路】由于插入数据时影响的只是插入数据到根节点间的关系。所以我们只需将插入数据通过双亲节点调到合适位置即可。 Tips:父节点和子节点关系 leftchild parent *2 1rightchild parent * 2 2parent (child - 1)/2 代码
void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp *p1;*p1 *p2;*p2 tmp;
}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;} }
}3.4 堆的删除 【代码思路】堆的删除默认是头删。删除有两种思路 ①将根节点删除再将其余数据全部向前移动。但这样做会造成一个问题挪动覆盖导致父子节点的关系全乱了需要重新建堆。为了删个数据重新建堆得不偿失所以我们采用下面这种方法。 ②:将堆顶的1数据和最后一个数据交换在删除最后一个数据。堆顶数据在通过向下调整算法调到合适位置即可。 代码
void HPPop(HP* php)
{assert(php);assert(!HPEmpty(php));//非空还有数据可删。该接口后面实现Swap(php-a[0], php-a[php-size - 1]);//交换php-size--;//删除//向下调整AdjustDown(php-a, php-size, 0);
}3.4.1 向下调整算法 【代码思路】向下调整算法有一个前提左右子树必须是一个堆才能调整。同时还要注意是调大堆还是小堆。 调小堆堆顶元素和孩子中最小的节点比较如果父节点大于较小的子节点子两者交换。不断向下调整到合适位置。调大堆和较大孩子比较 代码
void AdjustDown(HPDataType* a, int n, int parent)
{assert(a);int child parent * 2 1;//假设左孩子更小while (child n){//如果有孩子存在且有孩子更小则左孩子加1移到右孩子if ((child 1) n a[child] a[child 1]){child;}if (a[parent] a[child])//交换{Swap(a[parent], a[child]);parent child;child parent * 2 1;}else{//父节点小于较小的子节点说明已经调到合适位置此时break跳出break;}}
}3.5 堆的判空接下的过于简单直接给出带啊吗
bool HPEmpty(HP* php)
{return php-size 0;
}3.6 取堆顶的数据 assert(php);assert(!HPEmpty(php));//断言堆中还有元素return php-a[0];3.7 堆的个数
int HPSize(HP* php)
{assert(php);return php-size;
}3.8 堆的销毁
void HPDestory(HP* php)
{assert(php);php-a NULL;php-capacity php-size 0;
}四、所有代码
Heap.h
#pragma once#include stdio.h
#include assert.h
#include stdlib.h
#include stdbool.htypedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;void HPInit(HP* php);//初始化
void HPPush(HP* php, HPDataType x);//插入数据
void HPPop(HP* php);//删除数据
int HPTop(HP* php);//堆顶元素
bool HPEmpty(HP* php);//判空
int HPSize(HP* php);//数据个数
void HPDestory(HP* php);//销毁Heap.c
#include Heap.hvoid HPInit(HP* php)
{assert(php);php-a NULL;php-capacity 0;php-size 0;
}void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp *p1;*p1 *p2;*p2 tmp;
}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 AdjustDown(HPDataType* a, int n, int parent)
{assert(a);int child parent * 2 1;while (child n){if ((child 1) n a[child] a[child 1]){child;}if (a[parent] a[child]){Swap(a[parent], a[child]);parent child;child parent * 2 1;}else{break;}}
}void HPPush(HP* php, HPDataType x)
{assert(php);//扩容if (php-size php-capacity){int newcapacity php-size 0 ? 4 : php-capacity * 2;HPDataType* tmp (HPDataType*)realloc(php-a,sizeof(HPDataType) * newcapacity);if (tmp NULL){perror(malloc fail);exit(-1);}php-a tmp;php-capacity newcapacity;}php-a[php-size] x;php-size;//向上调整AdjustUp(php-a, php-size - 1);
}bool HPEmpty(HP* php)
{return php-size 0;
}void HPPop(HP* php)
{assert(php);assert(!HPEmpty(php));Swap(php-a[0], php-a[php-size - 1]);php-size--;//向下调整AdjustDown(php-a, php-size, 0);
}int HPTop(HP* php)
{assert(php);assert(!HPEmpty(php));return php-a[0];
}int HPSize(HP* php)
{assert(php);return php-size;
}void HPDestory(HP* php)
{assert(php);php-a NULL;php-capacity php-size 0;
}
