1、堆的概念
如果有一个关键码的集合 K = { k1 ，k2 ，k3 ，…，kn }，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并且 k(i) < k(i*2+1) 和 k(i) < k(i*2+2)， i = 0 ， 1 ， 2…，则称为小堆 ( 或大堆 ) 。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
堆的性质
- 堆中某个节点的值总是不大于或不小于其父节点的值；
- 堆总是一棵完全二叉树。
文章来源：https://www.toymoban.com/news/detail-649207.html
堆的存储结构
左边是逻辑结构，右边是存储结构文章来源地址https://www.toymoban.com/news/detail-649207.html
2、堆的实现
- 堆的构建
- 堆的销毁
- 堆的插入
- 堆的删除
- 取堆顶的数据
- 堆的数据个数
- 堆的判空
堆的构造与销毁
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 = 0; php->capacity = 0; }
堆的向上与向下调整
void swap(DataType*str1, DataType*str2) { DataType temp = *str1; *str1 = *str2; *str2 = temp; } //向上调整(前提是上面是一个堆) void AdjustUp(DataType* a, int child) { //利用孩子找父亲,并且比较 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 AdjustDown(int* a, int n, int parent)//n是数量 { //利用父亲找儿子并比较大小 int child = parent * 2 + 1; while (child < n) { //child + 1 < n可能没有右孩子，防止越界风险 if (child + 1 < n && a[child + 1] < a[child]) { child++; } // "<" 和 ">"取决与建立大小堆 if (a[child] > a[parent]) { swap(&a[child], &a[parent]); parent = child; int child = parent * 2 + 1; } else break; } }
堆的插入与堆的删除
//先插入一个数到数组的尾上，再进行向上调整算法，直到满足堆 void HeapPush(HP* php, DataType x) { assert(php); //判断是否要扩容 if (php->size == php->capacity) { int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2; DataType* temp = (DataType*)realloc(php->a, newCapacity * sizeof(DataType)); if (temp == NULL) { perror("realloc fail"); return; } php->a = temp; php->capacity = newCapacity; } php->a[php->size] = x; php->size++; AdjustUp(php->a, php->size - 1); } //删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据一换，然后删除数组 //最后一个数据，再进行向下调整算法。 void HeapPop(HP* php) { assert(php); swap(&php->a[0], &php->a[php->size - 1]); php->size--; AdjustDown(php->a, php->size, 0); }
堆的数据个数与堆的判空和取得堆的堆顶元素
DataType HeapTop(HP* php) { assert(php); assert(!HeapEmpty(php)); return php->a[0]; } bool HeapEmpty(HP* php) { assert(php); return php->size == 0; } int HeapSize(HP* php) { assert(php); return php->size; }
3、 建堆
向上调整建堆
// 向上调整建堆
for (int i = 1; i < n; i++)
{
Adjustup(a,i);
}向下调整建堆
// 向下调整建堆
for (int i = (n-1-1)/2; i >= 0; i--)
{
AdjustDown(a,n,i);
}到了这里，关于数据结构：堆的实现的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
