上海网站开发与设计,网站建设策划结束语,成都设计公司电话,企业网站托管哪家好前言#x1f49e;#x1f49e;
啦啦啦~这里是土土数据结构学习笔记#x1f973;#x1f973; #x1f4a5;个人主页#xff1a;大耳朵土土垚的博客 #x1f4a5; 所属专栏#xff1a;数据结构学习笔记 #x1f4a5;对于数据结构顺序表链表有疑问的都可以在上面数据结…前言
啦啦啦~这里是土土数据结构学习笔记 个人主页大耳朵土土垚的博客 所属专栏数据结构学习笔记 对于数据结构顺序表链表有疑问的都可以在上面数据结构的专栏进行学习哦~ 欢迎大家点赞✨收藏评论哦~ 有问题可以写在评论区或者私信我哦~ 一、 堆的概念及结构
如果有一个关键码的集合K { k1k2 k3 …kn-1 }把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中并满足ki k(2i1 )且 kik(2i2) ( ki k(2i1 )且 kik(2i2) ) i 012…则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆根节点最小的堆叫做最小堆或小根堆。 堆的性质 堆中某个节点的值总是不大于或不小于其父节点的值堆总是一棵完全二叉树。 ✨✨简单来说大堆指的是父节点都大于子节点的完全二叉树 小堆指的是父节点都小于子节点的完全二叉树 大堆的根节点是最大的小堆是最小的。 二、堆的实现
1.堆的创建
我们给出一个数组这个数组逻辑上可以看做一颗完全二叉树但是还不是一个堆现在我们通过算法把它构建成一个堆。根节点左右子树不是堆我们怎么调整呢这里我们从倒数的第一个非叶子节点的子树开始调整一直调整到根节点的树就可以调整成堆。 下面是堆创建以及实现堆所需的函数后文将一一介绍 #pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#includestdio.h
#includeassert.h
#includestdlib.h
typedef int HPDataType;
//构建一个结构体封装堆
typedef struct Heap
{HPDataType* a;//数组顺序表int size;//堆元素个数int capacity;//数组空间
}Heap;
//以下是实现堆的函数
// 堆的初始化
void HeapInit(Heap* hp);
// 堆的销毁
void HeapDestory(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HPDataType x);
// 堆的删除
void HeapPop(Heap* hp);
// 取堆顶的数据
HPDataType HeapTop(Heap* hp);
// 堆的数据个数
int HeapSize(Heap* hp);
// 堆的判空
int HeapEmpty(Heap* hp);
2.堆的初始化
void HeapInit(Heap* hp)
//堆的初始化
void HeapInit(Heap* hp)
{assert(hp);hp-a NULL;hp-capacity 0;hp-size 0;
}3.堆的删除删除堆顶元素
void HeapPop(Heap* hp) 在介绍堆的删除之前我们先介绍堆向下调整算法 显而易见堆的删除不可能像顺序表那样删除尾部元素size–就行我们需要玩点高深的删除顶部元素但删除顶部元素就没办法保证它删除后还是一个堆了这就要利用我们下面介绍的向下调整算法。 int a[] {1,8,3,5,7,6}; 该数组逻辑结构可以看成一个完全二叉树如下图所示 我们可以从图中看出它是一颗完全二叉树,但并不是所有的父节点都大于或小于其子节点所以不是一个堆接下来我们就可以通过下面介绍的堆向下调整算法将它调整为一个堆。 堆向下调整算法 现在我们给出一个数组逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。 向下调整算法有一个前提左右子树必须是一个堆才能调整。
int array[] {27,15,19,18,28,34,65,49,25,37};①下面介绍第一种向下调整为小堆 前提条件——左右子树都是小堆
//堆向下调整算法小堆
void AdjustDown(HPDataType* a, int n,int parent)
{int child parent * 2 1;//向下调整while (parent n){//找到较小的孩子节点if (child 1 n a[child] a[child 1]){child;}if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child child * 2 1;}elsebreak;}
}因为要调整为小堆所以要找到孩子中较小的一个进行比较 如果父节点小于较小的孩子节点则直接break不需要调整因为向下调整的前提条件是——左右子树都是小堆。 调整前 调整后 Swap函数在这里
//交换函数
void Swap(HPDataType* a,HPDataType* b)
{HPDataType tmp *a;*a *b;*b tmp;
}
②第二种向下调整为大堆前提条件——左右子树都是大堆
//堆向下调整算法大堆
void AdjustDown(HPDataType* 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 child * 2 1;}elsebreak;}
}因为要调整为大堆所以要找到孩子中较大的一个进行比较 如果父节点大于于较大的孩子节点则直接break不需要调整因为向下调整的前提条件是——左右子树都是大堆。 我们这里使用小堆向下调整大家可以根据自己的需求选择哦~ 学习完堆向下调整我们知道只要左右子树是一个堆那么我们就可以从根节点开始向下调整直到整个二叉树成为一个堆 所以删除堆顶元素我们就可以将堆顶元素与最后一个元素交换一下位置这样除了根节点其余父子关系都没变左右子树还是堆删除交换后的最后一个元素也就是原来的根节点 我们再利用堆向下调整算法将整个二叉树再次复原为堆。 堆顶元素删除
// 堆的删除删除堆顶元素
void HeapPop(Heap* hp)
{assert(hp);assert(!HeapEmpty(hp));//判空函数将在后文介绍//交换首尾元素Swap(hp-a[0], hp-a[hp-size - 1]);//size要记得--,表示删除元素hp-size--;//向下调整算法AdjustDown(hp-a, hp-size, 0);}
4.堆的插入
void HeapPush(Heap* hp, HPDataType x) 我们知道堆的父节点必须都大于或小于子节点那么往一个堆中插入元素是没办法保证大于或小于其父节点的所以我们插入之后需要调整这个二叉树来保证堆 这里就要用到堆向上调整算法了注意下面是小堆的调整 堆向上调整算法
//向上调整
void AdjustUp(HPDataType* a,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;}elsebreak;}
}堆向上调整类似于向下调整也有大堆小堆之分大家可以依照堆的向下调整自己试试看写一下大堆的向上调整 堆的插入
// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{assert(hp);//判断容量if (hp-size hp-capacity)//容量满了扩容{int newcapacity hp-capacity 0 ? 0 : 2 * hp-capacity;HPDataType* new (HPDataType*)realloc(hp-a, sizeof(HPDataType) * newcapacity);if (new NULL){perror(realloc fail);return;}hp-a new;hp-capacity newcapacity;}//尾插hp-a[hp-size] x;hp-size;//向上调整算法AdjustUp(hp-a,hp-size-1);
}这里要注意插入数据要判断容量如果满了要用realloc函数扩容对于realloc函数有疑问的可以看土土的动态内存函数博客——c语言动态内存函数介绍 如果第一次扩容就将空间扩为4个HPDataType其余扩原来的两倍 5. 取堆顶的数据
HPDataType HeapTop(Heap* hp);
// 取堆顶的数据
HPDataType HeapTop(Heap* hp)
{assert(hp);assert(!HeapEmpty(hp));//判空return hp-a[0];//顶即下标为0的元素
}6. 堆的数据个数
int HeapSize(Heap* hp)
// 堆的数据个数
int HeapSize(Heap* hp)
{assert(hp);return hp-size;
}堆的数据个数即为结构体中的size直接返回即可 7.堆的销毁
void HeapDestory(Heap* hp)
// 堆的销毁
void HeapDestory(Heap* hp)
{assert(hp);free(hp-a);hp-a NULL;hp-capacity 0;hp-size 0;
}在内存中用realloc函数开辟空间用 free释放即可 判空函数在这里~ int HeapEmpty(Heap* hp)
// 堆的判空
int HeapEmpty(Heap* hp)
{assert(hp);return hp-size 0;
}8.堆实现代码如下
#includeHeap.h
//堆的初始化
void HeapInit(Heap* hp)
{assert(hp);hp-a NULL;hp-capacity 0;hp-size 0;
}
// 堆的销毁
void HeapDestory(Heap* hp)
{assert(hp);free(hp-a);hp-a NULL;hp-capacity 0;hp-size 0;
}
//交换函数
void Swap(HPDataType* a,HPDataType* b)
{HPDataType tmp *a;*a *b;*b tmp;
}//堆向下调整算法
void AdjustDown(HPDataType* 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 child * 2 1;}elsebreak;}
}测试代码如下
#includeHeap.h
int main()
{Heap hp;HeapInit(hp);int a[] { 65,100,70,32,50,60 };for (int i 0; i 6; i){HeapPush(hp, a[i]);}while (!HeapEmpty(hp)){int top HeapTop(hp);printf(%d\n, top);HeapPop(hp);}return 0;}运行结果如下 居然是升序诶~大家知道原因吗 可以根据上面的代码和介绍理解为自己解答哦~
三、结语
以上就是堆的介绍和实现啦~✨✨需要注意的是堆有大堆小堆之分相应的函数也就有两种这里简单介绍了小堆的实现大堆介绍了一点大家可以通过上面介绍的自己探索大堆的实现此外堆向上调整与向下调整是一个重难点大家要多花时间去理解与记忆哦 ~完结撒花 ~
