怎么在word上做超链接网站,长沙做php的网站建设,c网站建设,做环卫车怎么做网站#x1f497;个人主页#x1f497; ⭐个人专栏——数据结构学习⭐ #x1f4ab;点击关注#x1f929;一起学习C语言#x1f4af;#x1f4ab; 导读#xff1a;
我们在前面学习了单链表和顺序表#xff0c;以及栈和队列。 今天我们来学习小堆。 关注博主或是订阅专栏个人主页 ⭐个人专栏——数据结构学习⭐ 点击关注一起学习C语言 导读
我们在前面学习了单链表和顺序表以及栈和队列。 今天我们来学习小堆。 关注博主或是订阅专栏掌握第一消息。
1. 堆的概念及结构
现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事一个是数据结构一个是操作系统中管理内存的一块区域分段。
1.1 什么是堆
堆是一种特殊的数据结构它可以看做是一个完全二叉树或者近似二叉树其中每个节点的值都大于等于或小于等于其子节点的值。在一个最大堆中根节点的值是最大的在一个最小堆中根节点的值是最小的。
1.2 堆的特点
堆的主要特点是每个节点的值都大于等于或小于等于其子节点的值。这种特点使得堆可以快速找到最大或最小的元素。另外堆还可以用于排序和优先队列等应用。 堆中兄弟节点的值之间没有关联。在堆中节点之间的关系仅由其在树中的位置决定。
1.3 堆的结构
堆通常使用数组来实现数组的下标代表节点在堆中的位置。根据节点在数组中的位置可以通过简单的计算得到其父节点、左子节点和右子节点的位置。这样在堆中插入一个新元素、删除堆顶的元素或者调整堆的结构时只需要对数组进行简单的操作而不需要改变整个堆的结构。
2. 堆的实现
我们需要创建两个 C文件: study.c 和 Heap.c以及一个 头文件 Heap.h。 头文件来声明函数一个C文件来定义函数另外一个C文件来用于主函数main进行测试。 堆的常见操作包括插入元素、删除堆顶元素、堆化调整堆的结构使其满足堆的特点等。其中插入元素和删除堆顶元素的时间复杂度为O(logn)堆化的时间复杂度为O(nlogn)。
3. 代码实现
3.1 定义结构体
Heap.h
typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size; //记录数组内的有效数据int capacity; //记录数组空间大小
}HP;3.2 堆的初始化
Heap.h
//堆的初始化
void HeapInit(HP* php);Heap.c
//堆的初始化
void HeapInit(HP* php)
{//各值初始化为0assert(php);php-a NULL;php-size 0;php-capacity 0;
}3.3 堆的销毁
我们的数组空间是用malloc函数开辟的使用完之后需要进行释放。 Heap.h
// 堆的销毁
void HeapDestroy(HP* php);Heap.c
// 堆的销毁
void HeapDestroy(HP* php)
{assert(php);free(php-a);php-a NULL;php-size 0;php-capacity 0;
}3.4 向上调整父节点与子节点
在出入数组后我们需要对数组进行调整以实现堆的结构特点。 在数组中下标*21就是他的子节点同样的下标-1/2就是他的父节点。 Heap.h
//向上调整父节点与子节点
void AdjustUp(HPDataType* a, int child);Heap.c
//交换父节点和子节点的值
void Swap(int* x, int* y)
{int tmp *x;*x *y;*y 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.5 堆的插入
Heap.h
// 堆的插入
void HeapPush(HP* php, HPDataType x);Heap.c
// 堆的插入
// 堆的插入
void HeapPush(HP* php, HPDataType x)
{assert(php);//首先检查数组容量是否足够if (php-size php-capacity){int newcapacity php-capacity 0 ? 4 : php-capacity * 2;HPDataType* tmp (HPDataType*)realloc(php-a, sizeof(HPDataType) * newcapacity);if (tmp NULL){perror(realloc fail);return;}php-a tmp;php-capacity newcapacity;}php-a[php-size] x;//在插入数值后需要检查是否要进行调整AdjustUp(php-a, php-size);php-size;
}3.6 向下调整父节点与子节点
删除堆是删除堆顶的数据但是我们无法直接删除第一个元素这有极大的可能会使我们的堆崩溃不再具有堆的特点而在删除之后把其它数值都往前移动再进行调整是一项很大的工作量。 所以我们可以将堆顶的数据根最后一个数据一换然后删除数组最后一个数据再进行向下调整算法。将当前的根数值调整到符合堆特点的位置去。 Heap.h
//向下调整父节点与子节点
void AdjustDown(int* a, int size, int parent);Heap.c
//向下调整父节点与子节点
void AdjustDown(int* a, int size, int parent)
{assert(a);int child parent * 2 1;//找到孩子节点while (child size){//找孩子中较小的一个if ((a[child] a[child 1]) (child 1) size){child 1;}//判断两个大小进行交换if (a[parent] a[child]){Swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break;}}
}3.7 堆的删除
Heap.h
// 堆的删除
void HeapPop(HP* php);Heap.c
// 堆的删除
void HeapPop(HP* php)
{assert(php);//先检查数组是否有可删除的数据assert(php-size 0);//交换首尾元素Swap(php-a[php-size - 1], php-a[0]);php-size--;//向下进行调整AdjustDown(php-a, php-size, 0);} 3.8 获取堆顶元素
返回数组首元素即可 Heap.h
// 取堆顶的数据
HPDataType HeapTop(HP* php);Heap.c
// 取堆顶的数据
HPDataType HeapTop(HP* php)
{assert(php);return php-a[0];
}3.9 获取堆的个数
直接返回size的值即可 Heap.h
// 堆的数据个数
size_t HeapSize(HP* php);Heap.c
// 堆的数据个数
size_t HeapSize(HP* php)
{assert(php);return php-size;
}3.10 堆的判空
只需判断size的值是否为0如果是返回true反之返回false。 Heap.h
// 堆的判空
bool HeapEmpty(HP* php);Heap.c
// 堆的判空
bool HeapEmpty(HP* php)
{assert(php);return php-size 0;
}4. 代码整理
4.1 Heap.h
#define _CRT_SECURE_NO_WARNINGS
#pragma once
#include stdio.h
#include stdlib.h
#include assert.h
#include stdbool.htypedef int HPDataType;typedef struct Heap
{HPDataType* a;int size; //记录数组内的有效数据int capacity; //记录数组空间大小
}HP;//堆的初始化
void HeapInit(HP* php);// 堆的销毁
void HeapDestroy(HP* php);// 堆的插入
void HeapPush(HP* php, HPDataType x);// 堆的删除
void HeapPop(HP* php);// 取堆顶的数据
HPDataType HeapTop(HP* php);// 堆的数据个数
size_t HeapSize(HP* php);// 堆的判空
bool HeapEmpty(HP* php);//向上调整父节点与子节点
void AdjustUp(HPDataType* a, int child);//向下调整父节点与子节点
void AdjustDown(int* a, int size, int parent);//交换父节点和子节点的值
void Swap(int* child, int* parent);4.2 Heap.c
#include Heap.h//堆的初始化
void HeapInit(HP* php)
{//各值初始化为0assert(php);php-a NULL;php-size 0;php-capacity 0;
}// 堆的销毁
void HeapDestroy(HP* php)
{assert(php);free(php-a);php-a NULL;php-size 0;php-capacity 0;
}//交换父节点和子节点的值
void Swap(int* x, int* y)
{int tmp *x;*x *y;*y 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 HeapPush(HP* php, HPDataType x)
{assert(php);//首先检查数组容量是否足够if (php-size php-capacity){int newcapacity php-capacity 0 ? 4 : php-capacity * 2;HPDataType* tmp (HPDataType*)realloc(php-a, sizeof(HPDataType) * newcapacity);if (tmp NULL){perror(realloc fail);return;}php-a tmp;php-capacity newcapacity;}php-a[php-size] x;//在插入数值后需要检查是否要进行调整AdjustUp(php-a, php-size);php-size;
}//向下调整父节点与子节点
void AdjustDown(int* a, int size, int parent)
{assert(a);int child parent * 2 1;//找到孩子节点while (child size){//找孩子中较小的一个if ((a[child] a[child 1]) (child 1) size){child 1;}//判断两个大小进行交换if (a[parent] a[child]){Swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break;}}
}// 堆的删除
void HeapPop(HP* php)
{assert(php);//先检查数组是否有可删除的数据assert(php-size 0);//交换首尾元素Swap(php-a[php-size - 1], php-a[0]);php-size--;//向下进行调整AdjustDown(php-a, php-size, 0);}// 取堆顶的数据
HPDataType HeapTop(HP* php)
{assert(php);return php-a[0];
}// 堆的数据个数
size_t HeapSize(HP* php)
{assert(php);return php-size;
}// 堆的判空
bool HeapEmpty(HP* php)
{assert(php);return php-size 0;
}4.3 study.c
void Test1()
{int array[] { 27,15,19,18,28,34,65,49,25,37 };HP hp;HeapInit(hp);for (int i 0; i sizeof(array) / sizeof(int); i){HeapPush(hp, array[i]);//插入数据}int k HeapSize(hp);while (k--){printf(%d , HeapTop(hp));HeapPop(hp);}HeapDestroy(hp);
}int main()
{;Test1();return 0;
}
