1. 堆的概念及结构
如果有一个关键码的集合K = { , , ,…, },把它的所有元素按完全二叉树的顺序存储方式存储
在一个一维数组中,并满足: <= 且 <= ( >= 且 >= ) i = 0,1,
2…,则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。
堆的性质:
堆中某个节点的值总是不大于或不小于其父节点的值;
堆总是一棵完全二叉树。
2. 堆的实现
1.堆的创建
下面我们给出一个数组,这个数组逻辑上可以看做一颗完全二叉树,但是还不是一个堆,现在我们通过算法,把它构建成一个堆。根节点左右子树不是堆,我们怎么调整呢?这里我们从倒数的第一个非叶子节点的子树开始调整,一直调整到根节点的树,就可以调整成堆。
int a[] = {1,5,3,8,7,6};
2. 建堆时间复杂度
因为堆是完全二叉树,而满二叉树也是完全二叉树,此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值,多几个节点不影响最终结果):
因此:建堆的时间复杂度为O(N)。
3.堆的插入
先插入一个10到数组的尾上,再进行向上调整算法,直到满足堆。
4.堆的删除
删除堆是删除堆顶的数据,将堆顶的数据根最后一个数据一换,然后删除数组最后一个数据,再进行向下调整算法。
5.堆向下调整算法
现在我们给出一个数组,逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提:左右子树必须是一个堆,才能调整。
3.代码深度解析
1.首先弄一个交换数据
交换两个指针所指向的变量的值
通过解引用操作符*,将p2指针所指向的变量的值赋给了p1指针所指向的变量,将之前存储在temp中的值赋给了p2指针所指向的变量,完成了交换。
void Swap(HPDataType *p1, HPDataType *p2) { HPDataType temp = *p1; *p1 =*p2; *p2 = temp; }
2.向上调整堆
将数组a中指定索引child的元素向上调整,使其在最小堆中满足最小堆的性质
通过计算child的父节点索引,即(parent = (child - 1) / 2),确定了父节点的位置。在循环中,child的元素比父节点的元素小调用Swap函数,将child和parent指向的元素进行交换。然后,代码更新child和parent的值,将child变为parent,parent变为(child - 1) / 2,继续循环。如果不是,即child的元素不小于父节点的元素,代码通过break语句跳出循环,这时已经完成了向上调整的操作。
void AdjudtUp(HPDataType* 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; } } }
3.向下调整堆
调整小顶堆的算法,接受一个int类型的指针a,表示一个数组,size表示数组的大小, parent表示要调整的节点位置
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; } } }
4.堆的插入
堆已满,则需要扩容。然后,将原来的内存空间指针hp->_a指向新分配的内存空间,更新堆的容量为新的容量。将要插入的元素x赋值给堆的最后一个位置hp->_a[hp->_size],然后增加堆的大小hp->_size++。最后,调用AdjustUp函数将新插入的元素向上调整,以维护堆的性质
void HeapPush(Heap* hp, HPDataType x) { assert(hp); if (hp->_size == hp->_capacity) { int newCapacity = hp->_capacity == 0 ? 4: hp->_capacity * 2; HPDataType*temp = (HPDataType*)realloc(hp->_a, newCapacity * sizeof(HPDataType)); if (temp == NULL) { perror("realloc fail"); exit(-1); } hp->_a =temp; hp->_capacity = newCapacity; } hp->_a[hp->_size] = x; hp->_size++; AdjudtUp(hp->_a,hp->_size-1); }
5.堆的创建
初始化后再通过for循环遍历数组a,并调用HeapPush函数将数组中的元素依次插入到堆中
void HeapCreate(Heap* hp, HPDataType *a, int n ) { assert(hp); hp->_size = 0; hp->_capacity =NULL; // 将数组a中的元素依次插入堆中 for (int i = 0; i < n; i++) { HeapPush(hp, a[i]); } }
6.堆的销毁
使用free函数释放堆的数组hp->_a的内存空间
void HeapDestory(Heap* hp) { assert(hp); free(hp->_a); hp->_a = NULL; hp->_size =hp->_capacity=0; }
7.堆的删除
调用AdjustDown()函数,从堆顶开始向下调整堆,以保持堆的性质
void HeapPop(Heap* hp) { assert(hp); assert(hp->_size > 0); Swap(&hp->_a[0], &hp->_a[hp->_size - 1]); hp->_size--; AdjustDown(hp->_a, hp->_size, 0); }
8.取堆顶的数据
函数返回堆中数组_a的第一个元素即堆顶的数据
取堆顶的数据
HPDataType HeapTop(Heap* hp) { assert(hp); assert(hp->_size > 0); return hp->_a[0]; }
9.堆的数据个数
返回堆的_size成员,即堆的大小
int HeapSize(Heap* hp) { assert(hp); return hp->_size; }
10. 堆的判空
通过断言assert(hp);来确保传入的参数hp不为NULL。
然后,通过判断堆的大小hp->_size是否为0来判断堆是否为空。
如果堆的大小为0,则返回1(即堆为空),否则返回0(即堆不为空)
int HeapEmpty(Heap* hp) { assert(hp); return hp->_size == 0; }
4.总的代码
1.heap.h
#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h> typedef int HPDataType; typedef struct Heap { HPDataType* _a; int _size; int _capacity; }Heap; //数据交换 void Swap(HPDataType* p1, HPDataType* p2); //向上堆的调整 void AdjudtUp(Heap* _a, int child); // 向下调整堆 void AdjustDown(int* a, int size, int parent); // 堆的构建 //void HeapCreate(Heap* hp);//, HPDataType* a, int n void HeapCreate(Heap* hp, HPDataType* a, int n); // 堆的销毁 void HeapDestory(Heap* hp); // 堆的插入 void HeapPush(Heap* hp, HPDataType x); // 堆的删除 void HeapPop(Heap* hp); // 取堆顶的数据 HPDataType HeapTop(Heap* hp); // 堆的数据个数 int HeapSize(Heap* hp); // 堆的判空 int HeapEmpty(Heap* hp);
2.Heap.c
#include"Heap.h" //交换数据 void Swap(HPDataType *p1, HPDataType *p2) { HPDataType temp = *p1; *p1 =*p2; *p2 = temp; } //向上调整堆 void AdjudtUp(HPDataType* 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 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 HeapPush(Heap* hp, HPDataType x) { assert(hp); if (hp->_size == hp->_capacity) { int newCapacity = hp->_capacity == 0 ? 4: hp->_capacity * 2; HPDataType*temp = (HPDataType*)realloc(hp->_a, newCapacity * sizeof(HPDataType)); if (temp == NULL) { perror("realloc fail"); exit(-1); } hp->_a =temp; hp->_capacity = newCapacity; } hp->_a[hp->_size] = x; hp->_size++; AdjudtUp(hp->_a,hp->_size-1); } // 堆的构建 //void HeapCreate(Heap* hp)//HPDataType* a, int n //{ // assert(hp); // hp->_size = 0; // 初始化堆的大小为0 // hp->_capacity = 0; // 设置堆的容量为n // hp->_a = NULL; // // 将数组a中的元素依次插入堆中 // //for (int i = 0; i < n; i++) { // // HeapPush(&hp, a[i]); // //} //} void HeapCreate(Heap* hp, HPDataType *a, int n ) { assert(hp); hp->_size = 0; // 初始化堆的大小为0 hp->_capacity =NULL; // hp->_a = NULL; // 将数组a中的元素依次插入堆中 for (int i = 0; i < n; i++) { HeapPush(hp, a[i]); } } // 堆的销毁 void HeapDestory(Heap* hp) { assert(hp); free(hp->_a); hp->_a = NULL; hp->_size =hp->_capacity=0; } // 堆的删除 void HeapPop(Heap* hp) { assert(hp); assert(hp->_size > 0); Swap(&hp->_a[0], &hp->_a[hp->_size - 1]); hp->_size--; AdjustDown(hp->_a, hp->_size, 0); } // 取堆顶的数据 HPDataType HeapTop(Heap* hp) { assert(hp); assert(hp->_size > 0); return hp->_a[0]; } // 堆的数据个数 int HeapSize(Heap* hp) { assert(hp); return hp->_size; } // 堆的判空 int HeapEmpty(Heap* hp) { assert(hp); return hp->_size == 0; }
2.Test.c
#include"Heap.h" void test() { Heap sl; int a[10] = { 10,8,2,4,5,3,6,7,9,1 }; /*HeapCreate(&sl); for (int i = 0;i < sizeof(a) / sizeof(int); i++) { HeapPush(&sl, a[i]); }*/ HeapCreate(&sl,a, sizeof(a) / sizeof(int)); while (!HeapEmpty(&sl)) { printf("%d ", HeapTop(&sl)); HeapPop(&sl); } printf("\n"); } int main() { test(); return 0; }