堆的向下调整算法和TOPK问题
目录
1.什么是堆？
1.1 向下调整建堆的时间复杂度计算
1.2 堆的结构体设计
2.堆的功能实现：
2.1 堆的插入：
2.2 堆的删除：
2.3 堆排序：
2.4 向下调整建堆：
2.5 TOPK问题：
2.6 向上调整算法：
2.7 向下调整算法：
2.8 堆的初始化/返回堆顶元素/返回堆内有效元素个数/堆的判空/堆的销毁
1.什么是堆？
首先
堆是一种完全二叉树，它一定满足所有的根结点都大于或小于它的左右子树
如果是大堆，那么堆顶的数就是堆中最大的数
如果是小堆，那么堆顶的数就是堆中最小的数
堆常常用来解决排序和TOPK问题
对于完全二叉树而已，若将结点从根结点开始，从0开始编号，那么
父节点 = (i-1)/2 (i-1)/2>=0
左孩子结点=(i*2)+1 (i*2)+1<n
右孩子结点=(i*2)+2 (i*2)+2<n
1.1 向下调整建堆的时间复杂度计算
首先需要知道二叉树的几个性质：
- 若规定二叉树的根结点的层数为1，那么二叉树的第i层有2^(i-1)棵结点
- 若规定二叉树的根结点的层数为1，那么一颗二叉树最多有2^(h)-1
- 对任意一颗二叉树，如果度为0为n0，度为2为n2，那么n0 = N2+1
- 若规定二叉树的根节点的层数为1， 具有n个结点的二叉树，其高度h为log(n+1)
根据性质去推算
从最后一个父节点开始，需要向下调整的次数：
T(h) = 2^0*(h-1) + 2^1*(h-2) + 2^2*(h-3) +.......+ 2^(h-3)*2 + 2^(h-2) *1
2*T(h) = 2^1*(h-1) + 2^2*(h-2) + 2^3*(h-3) +.......+ 2^(h-2)*2 +2^(h-1) *1
错位相减：2^1 + 2^2 + 2^3 ...... 2^(h-2) + 2^(h-1) - h +1
T(h) = 2^0+2^1 + 2^2 + 2^3 ...... 2^(h-2) + 2^(h-1) - h
T(h) = 2^h - 1 -h = N - Log(n+1)
采用大O的渐进表示法，建堆的时间复杂度就是O(N)
1.2 堆的结构体设计
#pragma once #include<stdio.h> #include<assert.h> #include<stdlib.h> #include<stdbool.h> typedef int HeapNodeDataType; typedef struct Heap { HeapNodeDataType* _a; int _size; int _capacity; }Heap; //堆向上调整 void AdjustUp(HeapNodeDataType* array, int n); //堆向下调整 void AdjustDown(HeapNodeDataType* array, int n, int size); //堆的初始化 void HeapInit(Heap* php); //堆的销毁 void HeapDestory(Heap* php); //堆的插入一个结点 void HeapPush(Heap* php, HeapNodeDataType data); //堆的删除一个结点 void HeapPop(Heap* php); //堆的出堆顶数据 HeapNodeDataType HeapTop(Heap* php); //返回堆内有效个数 int HeapSize(Heap* php); //交换函数 void Swap(HeapNodeDataType* a, HeapNodeDataType* b); //判断堆是否为空 bool HeapEmpty(Heap* php);
2.堆的功能实现：
2.1 堆的插入：
在尾部插入，向上调整，跟父节点比较，若满足条件就交换它们
void HeapPush(Heap* php, HeapNodeDataType data) { assert(php); if (php->_capacity == php->_size) { int newCapacity = php->_capacity == 0 ? 4 : php->_capacity * 2; HeapNodeDataType* newArray = (HeapNodeDataType*)realloc(php->_a, sizeof(HeapNodeDataType) * newCapacity); php->_a = newArray; php->_capacity = newCapacity; } php->_a[php->_size] = data; int child = php->_size; php->_size++; AdjustUp(php->_a, child); }
2.2 堆的删除：
将堆顶元素跟堆尾元素交换，然后从堆顶开始向下调整
void HeapPop(Heap* php) { assert(php); assert(php->_a); Swap(&php->_a[0], &php->_a[php->_size - 1]); php->_size--; AdjustDown(php->_a, 0, php->_size); }
2.3 堆排序：
利用向下调整算法建堆，然后将堆顶数据放到堆尾，堆内有效元素-1，再向下调整
void HeapSort(int* a, int n) { int parent = (n - 1 - 1) / 2; while (parent >= 0) { AdjustDown(a, parent, n); parent--; } for(int i = n - 1; i > 0; i--) { Swap(&a[0], &a[i]); AdjustDown(a, 0, i); } }
2.4 向下调整建堆：
从最后一个父节点（(end-1 )/2）开始向下调整建堆，到根结点向下调整建堆结束
void AdjustDown(HeapNodeDataType* array, int n, int size) { assert(array); int parent = n; int child = n * 2 + 1; if (child + 1 < size && array[child] > array[child + 1]) { child = n * 2 + 2; } while (child < size) { if (array[child] < array[parent]) { Swap(&array[child], &array[parent]); parent = child; child = parent * 2 + 1; if (child + 1 < size && array[child] > array[child + 1]) { child = parent * 2 + 2; } } else { break; } } }
2.5 TOPK问题：
首先取前K个元素向下调整建堆，然后遍历剩下的元素，若满足条件则进堆
如果是取前k个最大的数，那么就建小堆
如果是取前k个最小的数，那么就建大堆
void CreateNDate()//创建一个有100000个数的文件 { // int n = 100000; srand(time(0)); const char* file = "data.txt"; FILE* fin = fopen(file, "w"); if (fin == NULL) { perror("fopen error"); return; } for (size_t i = 0; i < n; ++i) { int x = rand() % 100000; fprintf(fin, "%d\n", x); } fclose(fin); } void PrintTopK(int k) { int* arr = (int*)malloc(sizeof(int) * k); const char* file = "data.txt"; FILE* fout = fopen(file, "r"); if (fout == NULL) { perror("fopen error"); return; } for (int i = 0; i < k; i++) { fscanf(fout,"%d", &arr[i]); } for (int i = (k - 1 - 1)/ 2; i >= 0; i--) { AdjustDown(arr, i, k); } int x = 0; while (fscanf(fout, "%d", &x) > 0) { if (x > arr[0]) { arr[0] = x; AdjustDown(arr, 0, k); } } printf("ǰ%d", k); for (int i = 0; i < k; i++) { printf("%d ", arr[i]); } printf("\n"); }
2.6 向上调整算法：
参数：需要数组的首元素地址，数组的有效元素个数
首先创建parent保存父亲结点
若父亲节点小于0则循环结束
判断父节点和子节点，若满足条件则交换，将父亲的值给孩子，继续求孩子结点的父节点
如果判断不需要交换则break
void AdjustUp(HeapNodeDataType* array, int n)
{
assert(array);
int child = n;
while (child > 0)
{
int parent = (child - 1) / 2;
if (array[child] > array[parent])
{
Swap(&array[child], &array[parent]);
child = parent;
}
else
{
break;
}
}
}2.7 向下调整算法：
参数：数组的首元素地址，从什么下表开始向下调整，数组的有效元素个数
已知父亲结点，求左孩子和右孩子结点，判断左右孩子的大小，假设法找到符合条件的哪一个
当孩子结点小于或等于堆内有效元素-1的时候进入循环，孩子结点大于size-1的时候循环结束
比较父子结点，判断是否需要交换
需要交换则将孩子给给父亲，运用假设法继续求孩子的结点中符合条件的那个
不需要交换则break
注意：在比较左右孩子谁满足条件时，需要判断右孩子是否存在，也即右孩子的下表需要小于size
void AdjustDown(HeapNodeDataType* array, int n, int size)
{
assert(array);
int parent = n;
int child = n * 2 + 1;
if (child + 1 < size && array[child] > array[child + 1])
{
child = n * 2 + 2;
}
while (child < size)
{
if (array[child] < array[parent])
{
Swap(&array[child], &array[parent]);
parent = child;
child = parent * 2 + 1;
if (child + 1 < size && array[child] > array[child + 1])
{
child = parent * 2 + 2;
}
}
else
{
break;
}
}
}2.8 堆的初始化/返回堆顶元素/返回堆内有效元素个数/堆的判空/堆的销毁
void HeapInit(Heap* php) { assert(php); php->_a = NULL; php->_capacity = php->_size = 0; } void HeapDestory(Heap* php) { assert(php); assert(php->_a); free(php->_a); php->_capacity = php->_size = 0; } HeapNodeDataType HeapTop(Heap* php) { assert(php); assert(php->_a); return php->_a[0]; } int HeapSize(Heap* php) { assert(php); return php->_size; } void Swap(HeapNodeDataType* a, HeapNodeDataType* b) { HeapNodeDataType tmp = *b; *b = *a; *a = tmp; } bool HeapEmpty(Heap* php) { return php->_size == 0; assert(php); }