网站建设模块化实现,西安seo关键词推广,工业设计产品设计案例,秦皇岛城乡建设局文章目录 写在前面1. 堆的概念和性质1.1 堆的概念1.2 堆的性质 2 堆的实现2.1 堆结构的定义2.2 堆的初始化2.3 堆的插入2.3.1 向上调整算法2.3.2 堆的插入元素过程 2.4 堆的删除2.4.1 向下调整算法2.4.2 堆的删除元素过程 2.5 获取堆顶元素2.6 获取堆元素个数2.7 判断堆是否为空… 文章目录 写在前面1. 堆的概念和性质1.1 堆的概念1.2 堆的性质 2 堆的实现2.1 堆结构的定义2.2 堆的初始化2.3 堆的插入2.3.1 向上调整算法2.3.2 堆的插入元素过程 2.4 堆的删除2.4.1 向下调整算法2.4.2 堆的删除元素过程 2.5 获取堆顶元素2.6 获取堆元素个数2.7 判断堆是否为空2.8 堆的销毁 写在前面
本片文章使用C语言实现了一种非线性的数据结构——堆小根堆。
1. 堆的概念和性质
1.1 堆的概念 如果有一个关键码的集合K {K0 k1 k2 …kn-1 }把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中并满足ki k2*i1且 ki k2*i2(ki k2*i1且 ki k~2*i2) i 012…则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆根节点最小的堆叫做最小堆或小根堆。 画个图理解一下
1.2 堆的性质
堆中某个节点的值总是不大于或不小于其父节点的值堆总是一棵完全二叉树。
2 堆的实现
由于堆的逻辑结构是一颗完全二叉树所以在实际存储时通常使用数组来表示这颗完全二叉树。
数组表示法的好处
由于完全二叉树的性质数组表示法可以将元素按照层级顺序依次存储不会有额外的空间浪费使得存储更为紧凑。数组的索引关系可以方便地表示父节点和子节点之间的关系。对于数组中的第 i 个元素其左子节点在 2i1 的位置右子节点在2i2 的位置而父节点在 (i−1) / 2的位置。
画个图理解一下
这种数组表示法使得堆的操作更加高效因为可以通过索引直接访问父子节点而无需使用指针。
2.1 堆结构的定义
从上面的分析可以知道堆结构的定义通常包括一个动态开辟的数组用来存储数据。为了方便扩容增加一个用于记录堆中元素个数以及一个用于记录堆容量的变量。 下面是堆结构的定义
typedef int HPDataType;
typedef struct Heap
{HPDataType* nums;//动态开辟的数组int size;//堆中元素个数int capacity;//堆容量
}Heap;2.2 堆的初始化
在初始时堆是一个空堆因此将堆的元素数组指针 nums 初始化为 NULL表示还没有分配存储空间。此时 capacity 为 0表示堆的容量为 0还没有存储任何元素。size 也为 0表示当前堆中的元素个数为 0。
这种初始化状态是堆数据结构的起始状态之后可以根据需要动态分配存储空间并通过插入元素来逐渐构建堆的结构。 代码如下
void HeapInit(Heap* php)
{assert(php);//检查参数有效性php-nums NULL;//初始化为 NULL,表示还没有分配存储空间php-size php-capacity 0;
}2.3 堆的插入
2.3.1 向上调整算法
在实现堆的插入之前需要介绍一下向上调整算法。这是因为向上调整算法是在堆的插入操作中使用的关键步骤。这算法确保在插入新元素后仍然保持堆的性质。 以下是向上调整算法的一般步骤
从插入的节点开始向上比较与父节点的大小。如果插入节点的值大于小于其父节点的值交换这两个节点。重复步骤 2 直到满足堆的性质或达到堆的根节点。
如向该小根堆{ 15181925283465492737 }插入一个10并用向上调整算法使该小根堆继续保持小根堆的性质
画个图理解一下 代码如下
//交换两个数
void Swap(HPDataType* x1, HPDataType* x2)
{HPDataType tmp *x1;*x1 *x2;*x2 tmp;
}
//向上调整算法
void AdjustUp(int* nums, int child)
{while (child 0){int parent (child - 1) / 2;//1.小堆 向上调整孩子小于父亲就交换//2.如果满足堆的性质则不需要调整//若实现大根堆这里nums[child] nums[parent]的 换成 if (nums[child] nums[parent]){Swap(nums[child], nums[parent]);}else{break;}child parent;}
}需要注意的是堆的向上调整算法的前提是插入位置之前的元素已经构成了一个有效的堆。这确保了插入新元素后通过向上调整以后整个堆仍然是一个有效的小顶堆。
2.3.2 堆的插入元素过程
在上面向上调整算法的介绍中我们发现向堆中插入元素时只需把新元素追加到堆的末尾然后通过向上调整算法使整个堆仍然是一个有效的堆。 堆的插入元素过程通常包括以下步骤
将新元素追加到堆的末尾。在堆的实现过程中我们是使用数组来表示堆的而在数组表示的堆中堆的末尾就是数组的最后一个位置因此新元素被添加到数组的最后一个位置。进行向上调整。 新元素与其父节点进行比较如果新元素的值小于其父节点的值它们交换位置。这个过程一直重复直到满足堆的性质即新插入的元素不再小于其父节点或者到达堆顶。
分析 3. 当堆为空时插入第一个元素时它天然满足堆的性质因此无需进行向上调整。 4. 当堆不为空时插入元素时就有可能会进行向上调整。这是因为插入的新元素被追加到堆的末尾与其父节点进行比较。如果新元素的值小于其父节点的值就会交换它们的位置。这个过程重复进行直到新插入的元素不再小于其父节点或者到达堆顶。
画个图理解一下
代码如下
void HeapPush(Heap* php, HPDataType x)
{assert(php);//检查参数有效性//检查是否需要扩容if (php-size php-capacity){int newcapacity php-capacity 0 ? 4 : php-capacity * 2;HPDataType* tmp (HPDataType*)realloc(php-nums, newcapacity * sizeof(HPDataType));if (tmp NULL){perror(HeapPush-realloc);exit(-1);}php-nums tmp;php-capacity newcapacity;}//插入新元素php-nums[php-size] x;//向上调整AdjustUp(php-nums, php-size - 1);
}2.4 堆的删除
2.4.1 向下调整算法
在实现堆的删除操作之前需要介绍一下向下调整算法。这是因为向下调整算法是在堆的删除操作中使用的关键步骤。向下调整算法通常在删除堆顶元素后使用确保新的堆顶元素能够找到适当的位置以维持堆的有序性。
确保向下调整算法有效的前提 堆的左右子树都满足堆的性质。这是因为向下调整算法的目的是将当前节点与其左右孩子中较小或较大具体取决于是小根堆还是大根堆的值交换以恢复堆的有序性。 如果堆的左右子树不满足堆的性质那么通过向下调整算法进行交换可能无法保证整个堆的有序性。因此在使用向下调整算法时必须确保该节点的左右子树都是堆。 向下调整算法具体步骤如下 找到较小的孩子 如果存在左右孩子找到值较小的孩子。如果当前节点有左孩子位置为 2 * parent 1如果有右孩子位置为 2 * parent 2。 比较与较小孩子的值 将当前节点与较小孩子的值比较。 交换或结束 如果当前节点的值大于较小孩子的值则交换它们并继续向下调整。如果当前节点的值小于等于较小孩子的值则调整结束。 循环 重复执行上述步骤直到当前节点不再有孩子或当前节点的值小于等于孩子的值。
画个图理解一下
代码如下
//交换两个数
void Swap(HPDataType* x1, HPDataType* x2)
{HPDataType tmp *x1;*x1 *x2;*x2 tmp;
}
void AdjustDown(int* nums, int n, int parent)
{// 左孩子的索引int child parent * 2 1;// 循环直到没有左孩子while (child n){// 如果右孩子存在且比左孩子小选择右孩子//若实现大根堆这里nums[child 1] nums[child]的 换成 if (child 1 n nums[child 1] nums[child]){child;}// 如果孩子比父亲小交换它们的值//若实现大根堆这里nums[child] nums[parent]的 换成 if (nums[child] nums[parent]){// 孩子比父亲大堆的有序性已经恢复退出循环Swap(nums[child], nums[parent]);}else{break;}// 更新父亲和孩子的索引parent child;child parent * 2 1;}
}2.4.2 堆的删除元素过程
堆的删除元素过程通常包括以下步骤
将堆顶元素与最后一个元素交换为了方便删除堆顶元素将堆顶元素与最后一个元素交换位置。删除堆顶元素将堆顶元素删除此时堆的大小减一。向下调整堆由于删除了堆顶元素需要通过向下调整算法保持堆的有序性。向下调整的目的是将交换后的堆顶元素放置到正确的位置使得堆仍然满足堆的性质。
画个图理解一下
代码如下
void HeapPop(Heap* php)
{assert(php);//检查参数有效性assert(!HeapEmpty(php));//检查堆是否为空Swap(php-nums[0], php-nums[php-size - 1]);php-size--;AdjustDown(php-nums, php-size - 1, 0);
}2.5 获取堆顶元素
获取堆顶元素步骤
堆不为空时才能取堆顶数据。获取堆顶元素的操作是直接访问堆数组的第一个元素因为在堆的表示中堆顶元素总是存储在数组的第一个位置。
代码如下
HPDataType HeapTop(Heap* php)
{assert(php);//检查参数有效性assert(!HeapEmpty(php));//检查堆是否为空return php-nums[0];
}2.6 获取堆元素个数
获取堆元素个数的操作可以直接返回堆的成员变量 size该变量记录了堆中当前元素的个数。 代码如下
int HeapSize(Heap* php)
{assert(php);//检查参数有效性return php-size;
}2.7 判断堆是否为空
判断堆是否为空的操作可以通过检查堆的成员变量 size 是否为零来实现。如果 size 为零表示堆中没有元素即堆为空否则堆非空。 代码如下
bool HeapEmpty(Heap* php)
{assert(php);//检查参数有效性return php-size 0;
}2.8 堆的销毁
在销毁堆的操作中我们首先使用 free 函数释放堆中的元素数组所占用的内存然后将数组指针设置为 NULL并将堆的大小和容量都设置为0表示堆已被销毁。这样的操作确保了在释放内存的同时将堆的状态清空防止野指针和内存泄漏的问题。 代码如下
void HeapDestroy(Heap* php)
{assert(php);//检查参数有效性free(php-nums);php-nums NULL;php-size php-capacity 0;
}至此本片文章就结束了若本篇内容对您有所帮助请三连点赞关注收藏支持下。 创作不易白嫖不好各位的支持和认可就是我创作的最大动力我们下篇文章见 如果本篇博客有任何错误请批评指教不胜感激
