dedecms 网站 经常无法连接,怎么做网站推广临沂,九龙坡做网站,wordpress浮动小人目录 1. 前言2. 堆的实现2.1 初始化2.2 插入2.2.1 分析2.2.1.1 情况一2.2.1.2 情况二2.2.1.3 情况三 2.2.2 插入代码实现2.2.2.1 向上调整代码 2.3 删除2.3.1 分析2.3.2 删除代码实现2.3.2.1 向下调整代码 2.4 找根节点数据2.5 元素个数2.6 判空2.7 销毁 3. 源代码3.1 Heap.h3.… 目录 1. 前言2. 堆的实现2.1 初始化2.2 插入2.2.1 分析2.2.1.1 情况一2.2.1.2 情况二2.2.1.3 情况三 2.2.2 插入代码实现2.2.2.1 向上调整代码 2.3 删除2.3.1 分析2.3.2 删除代码实现2.3.2.1 向下调整代码 2.4 找根节点数据2.5 元素个数2.6 判空2.7 销毁 3. 源代码3.1 Heap.h3.2 Heap.c3.3 test.c 1. 前言
在上一篇关于树和二叉树的博客中最后提到了堆。有小根堆和大根堆。 左边的结构是我们想象出来的右边才是实际存储的结构。 这次来实现堆。
2. 堆的实现
用数组来实现这里以实现小堆为例子它的特点是父节点小于子节点。 先定义一个堆的结构体为了方便扩容加了size。
typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;2.1 初始化
刚开始数组中没有数据置为NILL,此时的size和capacity都为0。 代码实现
void HeapInit(HP* php)
{assert(php);php-a NULL;php-size 0;php-capacity 0;
}2.2 插入
2.2.1 分析
2.2.1.1 情况一 假设插入的数据为30。 那么堆需要处理吗 在小堆中父亲节点小于子节点。 通过当前位置计算父节点的下标来判断一下是否需要调整显然28是小于30的这里就不需要调整了。
2.2.1.2 情况二
来看看其它情况 这里的子节点就小于父节点这里就要将父节点和子节点交换一下然后再判断。 通过下标将两个位置的值交换之后分析已经是小根堆了就不继续往前走了。
2.2.1.3 情况三 这里先将10与它的父节点28比较发现10比较小此时就交换它们两个再往上看发现18比10小又交换再往上发现15也比10小此时又交换。 此时就是这样 这个过程叫做向上调整。 只要发现父节点小于子节点时就停止向上调整。
2.2.2 插入代码实现
先判断空间是否足够不够就扩容够就直接插入x再将php-size。
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, newCapacity * sizeof(HPDataType));if (tmp NULL){perror(realloc fail);exit(-1);}php-a tmp;php-capacity newCapacity;}php-a[php-size] x;php-size;AdjustUp(php-a, php-size - 1);
}2.2.2.1 向上调整代码
从child的位置开始调整就是刚插入的值也就是size-1。 先和它的父节点比较如果小于父节点就交换。这里直接写成while循环交换之后向上走将child 的位置给parent然后parent (child - 1) / 2一直向上走当child0时结束或者parent 0时结束。
void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp *p1;*p1 *p2;*p2 tmp;
}void AdjustUp(HPDataType* a, int child)
{int parent (child - 1) / 2;//while (parent 0)while (child 0){if (a[child] a[parent]){Swap(a[child], a[parent]);child parent;parent (child - 1) / 2;//child (child - 1) / 2;//parent (parent - 1) / 2;}else{break;}}
}2.3 删除
规定删除堆顶数据。
2.3.1 分析 这时删除堆顶的数据那么堆顶就是次小的值。 这里要保持删除之后还是小堆。
如果使用挪动数据覆盖删除根此时整棵树的父子关系全乱了大小关系也乱了这样是不可行的。
使用首尾交换然后尾删。 尾删之后左右子树依旧是小堆。 把30换上去就结束了吗 当然不是使用向下调整算法。 此时不是小堆就要调整。 与30子节点18比较18小它们两个就交换。再向下25比18小又交换一次再向下27小于30又交换。最后到叶子节点就结束。
2.3.2 删除代码实现
首尾交换删除然后将php-size--最后向下调整。
void HeapPop(HP* php)
{assert(php);assert(php-size 0);Swap(php-a[0], php-a[php-size - 1]);php-size--;AdjustDown(php-a, php-size, 0);
}删三次
2.3.2.1 向下调整代码
当父节点大于子节点时就交换一下然后继续向下判断大小关系。 这里如果定义左右孩子左孩子小是一种逻辑右孩子小也是一种逻辑就很麻烦。 这里使用一个假设法就直接定义一个孩子。 假设左孩子小如果解设错了更新一下换到右孩子。 如果孩子小于父亲就交换然后向下走让parent childchild parent * 2 1。
void AdjustDown(int* a, int size, int parent)
{int child parent * 2 1;while (child size){// 假设左孩子小如果解设错了更新一下if (child 1 size a[child 1] a[child]){child;}if (a[child] a[parent]){Swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break;}}
}2.4 找根节点数据
堆顶数据在数组中的位置就是php-a[0]。
HPDataType HeapTop(HP* php)
{assert(php);assert(php-size 0);return php-a[0];
}2.5 元素个数
元素的个数就是这个数组的长度直接返回php-size。
size_t HeapSize(HP* php)
{assert(php);return php-size;
}2.6 判空
直接判断一下数组中是否有数据就行如果php-size 0为真就是空为假就不是。
bool HeapEmpty(HP* php)
{assert(php);return php-size 0;
}2.7 销毁
先断言一下然后将数组free再将php-a 置为NULL最后将php-size 和 php-capacity 置为0。
void HeapDestroy(HP* php)
{assert(php);free(php-a);php-a NULL;php-size php-capacity 0;
}3. 源代码
3.1 Heap.h
#pragma once
#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.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);
3.2 Heap.c
#includeHeap.h// 小堆
void HeapInit(HP* php)
{assert(php);php-a NULL;php-size 0;php-capacity 0;
}void HeapDestroy(HP* php)
{assert(php);free(php-a);php-a NULL;php-size php-capacity 0;
}void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp *p1;*p1 *p2;*p2 tmp;
}void AdjustUp(HPDataType* a, int child)
{int parent (child - 1) / 2;//while (parent 0)while (child 0){if (a[child] a[parent]){Swap(a[child], a[parent]);child parent;parent (child - 1) / 2;//child (child - 1) / 2;//parent (parent - 1) / 2;}else{break;}}
}// O(logN)
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, newCapacity * sizeof(HPDataType));if (tmp NULL){perror(realloc fail);exit(-1);}php-a tmp;php-capacity newCapacity;}php-a[php-size] x;php-size;AdjustUp(php-a, php-size - 1);
}void AdjustDown(int* a, int size, int parent)
{int child parent * 2 1;while (child size){// 假设左孩子小如果解设错了更新一下if (child 1 size 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* php)
{assert(php);assert(php-size 0);Swap(php-a[0], php-a[php-size - 1]);php-size--;AdjustDown(php-a, php-size, 0);
}HPDataType HeapTop(HP* php)
{assert(php);assert(php-size 0);return php-a[0];
}size_t HeapSize(HP* php)
{assert(php);return php-size;
}bool HeapEmpty(HP* php)
{assert(php);return php-size 0;
}3.3 test.c
#includeHeap.hint main()
{int a[] { 4,6,2,1,5,8,2,9};HP hp;HeapInit(hp);for (int i 0; i sizeof(a) / sizeof(int); i){HeapPush(hp, a[i]);}/*int k 3;while (k--){printf(%d\n, HeapTop(hp));HeapPop(hp);}*/while (!HeapEmpty(hp)){printf(%d , HeapTop(hp));HeapPop(hp);}printf(\n);return 0;
}
