免费自助建站网站建设免费信息发布,专业做网站哪家强,用备案的网站做违法网站,wordpress安装系统#x1f3a5; 屿小夏 #xff1a; 个人主页 #x1f525;个人专栏 #xff1a; 数据结构解析 #x1f304; 莫道桑榆晚#xff0c;为霞尚满天#xff01; 文章目录 #x1f324;️前言#x1f324;️堆的理论☁️二叉树的顺序存储☁️堆的概念 #x1f324;️堆的实现… 屿小夏 个人主页 个人专栏 数据结构解析 莫道桑榆晚为霞尚满天 文章目录 ️前言️堆的理论☁️二叉树的顺序存储☁️堆的概念 ️堆的实现逻辑☁️堆向下调整算法☁️建堆☁️建堆时间复杂度☁️堆的插入☁️堆的删除 ️堆的代码是实现☁️堆的结构体☁️堆的初始化☁️堆的销毁☁️堆的插入☁️堆的删除☁️取堆顶数据☁️堆的数据个数☁️堆的判空 ️堆特性总结️全篇总结 ️前言 堆是一种基本而强大的数据结构。本文将深入探讨堆的概念、原理以及实现。 ️堆的理论
☁️二叉树的顺序存储
普通的二叉树是不适合用数组来存储的因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事一个是数据结构一个是操作系统中管理内存的一块区域分段。 ☁️堆的概念 堆的性质
堆中某个节点的值总是不大于或不小于其父节点的值堆总是一棵完全二叉树。 ️堆的实现逻辑
☁️堆向下调整算法
一个数组逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整 成一个小堆。向下调整算法有一个前提左右子树必须是一个堆才能调整。
int array[] {27,15,19,18,28,34,65,49,25,37};☁️建堆
给定一个数组,这个数组逻辑上可以看做一颗完全二叉树但是还不是一个堆这个时候就需要我们通过算法把它构建成一个堆。根节点左右子树不是堆我们从倒数的第一个非叶子节点的子树开始调整一直调整到根节点的树就可以调整成堆(向下调整)。
int a[] {1,5,3,8,7,6};☁️建堆时间复杂度
因为堆是完全二叉树而满二叉树也是完全二叉树此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值多几个节点不影响最终结果) 根据上图可以推算出: 建堆的时间复杂度为O(N)。
☁️堆的插入
先插入一个10到数组的尾上再进行向上调整算法直到满足堆。 ☁️堆的删除
删除堆是删除堆顶的数据将堆顶的数据根最后一个数据一换然后删除数组最后一个数据再进行向下调整算法。 ️堆的代码是实现
☁️堆的结构体
typedef int HeapDataType;typedef struct Heap
{HeapDataType* a;int size; //有效元素int cpciti; //容量
}HP;HeapDataType 定义了堆中元素的数据类型这里是整数。struct Heap 定义了一个包含堆数据的结构体包括一个指向堆数组的指针 堆的有效元素个数 以及堆的容量 。
☁️堆的初始化
void HeapInit(HP* hp)
{assert(hp);hp-a NULL;hp-size hp-cpciti 0;
}首先使用 断言来确保传入的指针 不为空。然后将堆数组指针设置为 NULL将堆的有效元素个数和容量都初始化为 0。
☁️堆的销毁
void HeapDestroy(HP* hp)
{assert(hp);free(hp-a);hp-a NULL;hp-size hp-cpciti 0;
}使用 断言确保传入的指针 不为空。然后使用函数释放堆数组分配的内存并将指针设置为 NULL。最后将堆的有效元素个数和容量都设置为 0。
☁️堆的插入
void AdjustUp(HeapDataType* a, int child)
{int parent (child - 1) / 2;while (child 0){if (a[child] a[parent]){Swap(a[child], a[parent]);child parent;parent (parent - 1) / 2;}else{break;}}
}
void HeapPush(HP* hp, HeapDataType x)
{assert(hp);//if (hp-size hp-cpciti){int newCapacity hp-cpciti 0 ? 4 : hp-cpciti * 2;HeapDataType* tmp (HeapDataType*)realloc(hp-a, sizeof(HeapDataType) * newCapacity);if (tmp NULL){perror(realloc fail);exit(-1);}hp-a tmp;hp-cpciti newCapacity;}hp-a[hp-size] x;hp-size;AdjustUp(hp-a, hp-size-1);
}AdjustUp用于将堆的最后一个节点即插入的新节点向上调整使得以新节点为叶子节点的子树仍然满足堆的性质。具体步骤如下
初始化parent为(child - 1) / 2即新节点的父节点。如果child大于0即child不是根节点则执行以下操作 如果child节点的值小于parent节点的值则交换child和parent节点的值并更新child为parentparent为(child - 1) / 2。否则跳出循环。 调整结束。
HeapPush用于向堆中插入一个新的元素。具体步骤如下
检查堆的大小是否达到了容量上限如果是则进行扩容操作。将新元素x放入堆的最后一个位置。堆的大小加1。调用AdjustUp函数将新插入的元素向上调整。
☁️堆的删除
void AdjustDown(HeapDataType* a, int n, int parent)
{int child parent * 2 1;while (child n){if (child 1 n a[child 1] a[child]){child;}if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break;}}
}
void HeapPop(HP* hp)
{assert(hp);assert(hp-size 0);Swap(hp-a[0], hp-a[hp-size - 1]);hp-size--;AdjustDown(hp-a,hp-size,0);
}AdjustDown用于将堆的根节点向下调整使得以根节点为根的子树仍然满足堆的性质。具体步骤如下
初始化child为parent的左孩子节点。如果child小于n即child在数组范围内则执行以下操作 如果child1也小于n且右孩子节点的值小于左孩子节点的值则将child更新为右孩子节点。如果child节点的值小于parent节点的值则交换child和parent节点的值并更新parent为childchild为parent的左孩子节点。否则跳出循环。 调整结束。
HeapPop用于删除堆的根节点。具体步骤如下
交换根节点和最后一个节点的值。将堆的大小减1。调用AdjustDown函数将根节点向下调整。
☁️取堆顶数据
HeapDataType HeapTop(HP* hp)
{assert(hp);assert(hp-size 0);return hp-a[0];
}断言来确保传入的指针 是非空的不为 NULL以及堆的大小大于0。如果这些条件不满足程序会终止执行。然后返回堆的顶部元素也就是堆数组中的第一个元素。
☁️堆的数据个数
int HeapSize(HP* hp)
{return hp-size;
}size即堆的大小表示堆中当前包含的元素个数。
☁️堆的判空
int HeapEmpty(HP* hp)
{assert(hp);return hp-size 0;
}断言确保传入的指针不为空检查堆的大小是否等于0。如果堆的大小为0函数返回1表示堆为空否则返回0表示堆不为空。
️堆特性总结
堆是一棵完全二叉树即除了最后一层外其他层都是满的最后一层从左到右填满。堆分为大根堆和小根堆两种大根堆中每个节点的值都大于其子节点的值小根堆中每个节点的值都小于其子节点的值。堆的根节点是堆中的最小或最大元素。堆中的任意节点的值都小于或大于其子节点的值。堆中的元素是按照层序遍历的顺序存储在数组中的可以用数组来实现堆。堆的插入和删除操作分别为向上调整AdjustUp和向下调整AdjustDown保证插入和删除后仍然满足堆的性质。堆的时间复杂度为O(logN)其中N为堆中元素的个数。
️全篇总结
堆作为数据结构中的重要部分展现了在多种算法和应用中的价值。掌握堆的知识会对你以后解决各种问题和优化性能提供重要帮助。
