目录
堆是一种数据结构,它是由一组元素组成的,并按照一定的规则进行排序和访问。堆可以看作是一个完全二叉树,其中每个节点的值都大于或等于其子节点(对于最大堆)或小于或等于其子节点(对于最小堆)。堆通常用来解决具有优先级的问题,例如找到最大或最小的元素。
堆的性质:
- 堆中某个节点的值总是不大于或不小于其父节点的值;
- 堆总是一棵完全二叉树。
这里写的是小根堆,大根堆可以在小根堆的基础上稍作修改。下面是堆要实现的一些接口函数:
//初始化堆void HeapInit(HP* php);//销毁堆void HeapDestory(HP* php);//插入元素void HeapPush(HP* php, HPDataType x);//堆向上调整算法void AdjustUp(HP* php, int x);//弹出堆顶元素void HeapPop(HP* php);//堆向下调整算法void AdjustDwon(HPDataType* a, int size, int x);//取堆顶元素HPDataType HeapTop(HP* php);//返回堆的大小int HeapSize(HP* php);//判断是否为空bool HeapEmpty(HP* php);//打印堆void HeapPrint(HP* php);
堆的定义:
typedef int HPDataType;typedef struct Heap{HPDataType* a;int size;int capacity;}HP;
对于一些简单的接口函数,我们就不详细介绍了,在堆中,我们主要要学习的是向上调整算法和向下调整算法。这两个函数分别在插入元素和弹出元素的时候会调用。
2.1初始化堆
void HeapInit(HP* php){assert(php);php->a = NULL;php->size = php->capacity = 0;}
2.2销毁堆
void HeapDestory(HP* php){assert(php);free(php->a);php->a = NULL;php->size = php->capacity = 0;}
2.3取堆顶元素
HPDataType HeapTop(HP* php){assert(php);return php->a[0];}
2.4返回堆的大小
int HeapSize(HP* php){assert(php);return php->size;}
2.5判断是否为空
bool HeapEmpty(HP* php){assert(php);return php->size == 0;}
2.6打印堆
void HeapPrint(HP* php){assert(php);for (int i = 0; i < php->size; i++){printf("%d ", php->a[i]);}printf("\n");}
2.7插入元素
向堆中插入一个元素,我们可以将这个元素插入到堆的尾部,因为堆的实际存储结构是一个数组,我们可以将元素放到数组末尾,但如果仅仅是插入到数组末尾的话,会将堆的结构给破环,我们还需要调用一个向上调整的函数,来调整各个节点间的大小关系。
在插入之前,需要判断堆的容量是否足够,如果堆的容量已满,需要扩容,这里每次扩容实在原来的基础上扩2倍。
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, sizeof(HPDataType) * newCapacity);if (tmp == NULL){printf("realloc fail\n");exit(-1);}php->a = tmp;php->capacity = newCapacity;}php->a[php->size] = x;AdjustUp(php->a, php->size);//向上调整php->size++;}
2.8堆的向上调整
在上面插入元素的过程中,我们已经使用了堆的向上调整算法,下面,我们来看看怎么实现这个向上调整算法吧:
先插入一个10到数组的尾上,再进行向上调整算法,直到满足堆。
图示过程:
void AdjustUp(HPDataType* a, int x){int child = x;int parent = (child - 1) / 2;while (child > 0){if (a[child] < a[parent]){Swap(&a[child], &a[parent]);}else{break;}child = parent;parent = (child - 1) / 2;}}
代码分析:
- 初始化变量child为节点x,parent为其父节点的索引,也即 (child - 1) / 2。
- 进入一个循环,该循环会一直执行直到节点x上浮到合适的位置或者到达堆顶。
- 在循环中,判断节点x的值是否小于其父节点的值,若成立则交换两者的值。
- 若节点x的值不小于父节点的值,则跳出循环,因为此时堆的性质已满足。
- 更新child和parent的值,将child更新为parent,parent更新为其父节点的索引,也即 (child - 1) / 2。
- 重复步骤3-5,直到节点x的值大于或等于其父节点的值,或者到达堆顶。
2.9弹出元素
弹出元素就是将堆顶的元素给删除,但我们不能直接进行删除,这样会将堆的结构给破坏,正确的方法是先将堆顶的元素和最后的元素进行交换,这样保证的首元素的左子树和右子树依然是堆的形态,然后将size自减,最后调用一个堆的向下调整函数。
void HeapPop(HP* php){assert(php);Swap(&php->a[0], &php->a[php->size-1]);php->size--;AdjustDwon(php->a, php->size, 0);}
2.10堆的向下调整
堆的向下调整:每次将父节点和左右孩子的较小值进行交换(小根堆),不断地更新父节点的孩子节点的值。
void AdjustDwon(HPDataType* a, int size, int x){int parent = x;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]);}else{break;}parent = child;child = parent * 2 + 1;}}
- 初始化变量parent为节点x,child为其左子节点的索引,也即 parent * 2 + 1。
- 进入一个循环,该循环会一直执行直到节点x下沉到合适的位置或者没有子节点。
- 在循环中,首先判断节点x是否有右子节点,并且右子节点的值小于左子节点的值,如果成立则将child更新为右子节点的索引。
- 接着判断节点x的值是否大于其子节点的值,若成立则交换两者的值。
- 若节点x的值不大于子节点的值,则跳出循环,因为此时堆的性质已满足。
- 更新parent和child的值,将parent更新为child,child更新为parent的左子节点的索引,也即 parent * 2 + 1。
- 重复步骤3-6,直到节点x的值小于或等于其子节点的值,或者没有子节点。
因为堆是完全二叉树,而满二叉树也是完全二叉树,此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值,多几个节点不影响最终结果):
向下调整:
因此:向下调整建堆的时间复杂度为O(N)。
向上调整:
因此:向上调整建堆的时间复杂度为N*logN;
4.1 堆排序
利用堆排序数组并打印出来:
void testHeapSort(){HP hp;HeapInit(&hp);int a[] = { 1,4,7,5,10,2,8,9,3,6 };for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++){HeapPush(&hp, a[i]);}while (!HeapEmpty(&hp)){printf("%d ", HeapTop(&hp));HeapPop(&hp);}//释放内存HeapDestory(&hp);}int main(){testHeapSort();return 0;}
输出结果:
但是,使用这种方法是不是有点复杂了呢?我们要进行堆排序,还得先写一个堆的数据结构,当然并不是这样的,我们可以将代码进行修改,在原数组上进行建堆:
思路:
对于在原数组上进行建堆,我们可以使用两种方式:
第一种是向上建堆,向上建堆的时间复杂度是 O(N*logN),我们不推荐使用这种方法。
第二种是向下建堆,它的时间复杂度是O(N),它的效率比向上建堆要高。我们推荐使用向下建堆。
还有一个比较让人难以理解的一点是:如果要进行升序,我们要建大堆,如果要进行降序,我们要建小堆。
void swap(int* x, int* y){int tmp = *x;*x = *y;*y = tmp;}void HeapSort(int* a, int n){//从倒数第一个非叶子节点开始调for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDwon(a, n, i);//向下调整建堆}int end = n - 1;while (end > 0){swap(&a[0], &a[end]);AdjustDwon(a, end, 0);//向下调整[0,end]的元素--end;}}int main(){int a[] = { 1,4,7,5,10,2,8,9,3,6 };int n = sizeof(a) / sizeof(a[0]);HeapSort(a,n);//堆排序for (int i = 0; i < n; i++){printf("%d ", a[i]);}return 0;}
4.2 TOP-K问题
TOP-K问题:即求数据结合中前K个最大的元素或者最小的元素,一般情况下数据量都比较大。
比如:专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
对于Top-K问题,能想到的最简单直接的方式就是排序,但是:如果数据量非常大,排序就不太可取了(可能 数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决,基本思路如下:
用数据集合中前K个元素来建堆
- 前k个最大的元素,则建小堆
- 前k个最小的元素,则建大堆
用剩余的N-K个元素依次与堆顶元素来比较,不满足则替换堆顶元素
将剩余N-K个元素依次与堆顶元素比完之后,堆中剩余的K个元素就是所求的前K个最小或者最大的元素。
实际应用:在10000000个随机数中找出前十个最大的数字
void AdjustDwon(int* a, int size, int x){int parent = x;int child = parent * 2 + 1;while (child < size){if (child + 1 < size && a[child + 1] < a[child]){child++;}if (a[child] < a[parent]){int tmp = a[child];a[child] = a[parent];a[parent] = tmp;}else{break;}parent = child;child = parent * 2 + 1;}}void PrintTopK(int* a, int n, int k){int* KMaxHeap = (int*)malloc(sizeof(int) * k);assert(KMaxHeap);for (int i = 0; i < k; i++){KMaxHeap[i] = a[i];}//建小根堆for (int i = (k - 1 - 1) / 2; i >= 0; i--){AdjustDwon(KMaxHeap, k, i);}//依次比较a数组中剩余的元素for (int i = k; i < n; i++){if (a[i] > KMaxHeap[0]){KMaxHeap[0] = a[i];}AdjustDwon(KMaxHeap, k, 0);}//打印for (int i = 0; i < k; i++){printf("%d ", KMaxHeap[i]);}}void testTopK(){srand(time(0));int n = 10000000;int* a = (int*)malloc(sizeof(int) * n);for (int i = 0; i < n; i++){a[i] = rand() % n;//a[i]的范围[1,n]}//手动设定10个最大的数a[2] = n + 3;a[122] = n + 5;a[1233] = n + 1;a[12333] = n + 2;a[1322] = n + 8;a[2312] = n + 6;a[54612] = n + 7;a[546612] = n + 9;a[5612] = n + 10;a[46612] = n + 4;PrintTopK(a, n, 10);}int main(){testTopK();return 0;}
来源地址:https://blog.csdn.net/m0_73648729/article/details/132268305