赞
踩
普通的二叉树是不适合用数组来存储的,因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(完全二叉树)
使用顺序结构的数组来存储
,需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事
,一个是数据结构,一个是操作系统中管理内存的一块区域分段。
堆的性质:
将堆(完全二叉树)看作顺序表,利用顺序表存储堆中的值。结构如下:
typedef int HPDataType;
typedef struct Heap
{
HPDataType* a;
int size;
int capacity;
}HP;
实际就是顺序表的那一套。
void HPInit(HP* php) { assert(php); php->a = NULL; php->size = php->capacity = 0; } void HPDestory(HP* php) { assert(php); free(php->a); php->a = NULL; php->size = php->capacity = 0; } bool HPEmpty(HP* php) { assert(php); return php->size == 0; } void HPPrint(HP* php) { assert(php); for (int i = 0; i < php->size; i++) { printf("%d ", php->a[i]); } printf("\n"); }
void Swap(HPDataType* x, HPDataType* y)
{
HPDataType tmp = *x;
*x = *y;
*y = tmp;
}
HPDataType HPTop(HP* php)
{
assert(php);
assert(php->size > 0);
return php->a[0];
}
堆的插入:在已知是堆的条件下进行尾插,利用堆向上调整算法使其依旧保持堆的特征。
堆向上调整算法:
例如:先插入一个10到数组的尾上,再进行向上调整算法,直到满足堆。
void AdjustUp(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 HPPush(HP* php, HPDataType x) { assert(php); //容量满了——>扩容 if (php->size == php->capacity) { int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity; HPDataType* tmp = (HPDataType*)realloc(php->a, newcapacity * sizeof(HPDataType)); if (tmp == NULL) { perror("realloc fail!"); return; } php->a = tmp; php->capacity = newcapacity; } //尾插 php->a[php->size++] = x; //向上调整算法 AdjustUp(php->a, php->size - 1); }
堆的删除:在已知是堆的条件下删除堆顶的数据(堆的尾删无意义依旧是堆),先将堆顶与堆尾的数据进行交换,再删除堆尾的数据,最后利用堆向下调整算法,将堆顶向下调整,使其依旧保持堆的特征。
堆向下调整算法:
例如:现在我们给出一个数组,逻辑上看做一颗完全二叉树。我们通过从根结点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提:左右子树必须是都是堆,才能调整
。
void AdjustDown(HPDataType* a, int n, int parent) { //假设左孩子小 int child = 2 * parent + 1; while (child < n) { //找出真正小的那个孩子 if (child + 1 < n && 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 HPPop(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); }
//假设模拟php->a[] = {19,34,65,18,15,28};
void AdjustUpCreateHeap(HP* php) { //根节点不需调整,从第二个节点开始调整 for (int i = 1; i < php->size; i++) { AdjustUp(php->a, i); } } int main() { HP hp; HPInit(&hp); hp.a = (HPDataType*)malloc(sizeof(HPDataType) * 6); hp.a[0] = 19; hp.a[1] = 34; hp.a[2] = 65; hp.a[3] = 18; hp.a[4] = 15; hp.a[5] = 28; hp.size += 6; hp.capacity += 6; AdjustUpCreateHeap(&hp); HPPrint(&hp); //15 18 28 34 19 65 }
计算向上调整算法建堆时间复杂度:
因为堆是完全⼆叉树,而满⼆叉树也是完全⼆叉树,此处为了简化使用满⼆叉树来证明(时间复杂度本来看的就是近似值,多几个结点不影响最终结果)
//假设模拟php->a[] = {19,34,65,18,15,28};
void AdjustDownCreateHeap(HP* php) { //叶子节点不需调整,从倒数第一个非叶子节点开始调整 for (int i = (php->size - 1 - 1) / 2; i >= 0; i--) { AdjustDown(php->a, php->size, i); } } int main() { HP hp; HPInit(&hp); hp.a = (HPDataType*)malloc(sizeof(HPDataType) * 6); hp.a[0] = 19; hp.a[1] = 34; hp.a[2] = 65; hp.a[3] = 18; hp.a[4] = 15; hp.a[5] = 28; hp.size += 6; hp.capacity += 6; AdjustDownCreateHeap(&hp); //15 18 28 19 34 65 HPPrint(&hp); }
计算向下调整算法建堆时间复杂度:
TOP-K问题:即求数据个数N中前K个最大的元素或者最小的元素,一般情况下数据量都比较大。
对于Top-K问题,能想到的最简单直接的方式就是排序,但是:如果数据量非常大,排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决,基本思路如下:
前置知识:
1 GB = 1024 MB = 1024*1024 KB = 1024*1024*1024 Byte
(大约10.7亿Byte)40 / 10.7 近似:3.72GB内存
问题一
:假设只有4GB内存,要在10亿个整数中,如何找出最大的前10个数?
方法:
O(n)
O(10 * logn) = O(logn)
(10忽略不计)总时间复杂度:O(n)
; 空间复杂度:O(n)
问题二
:假设只有1GB内存,在这些磁盘文件中,取最大的前10个数。
方法:
虽然节省了一些内存,但是依旧要花费相当大的内存,而且频繁的读取数据效率低。有无不需要花费多少内存就能完成的呢?
问题三
:假设只有1KB内存,在这些磁盘文件中,取最大的前10个数。
方法:
时间复杂度:O(k)
时间复杂度:O((n-k) * logk)
总时间复杂度:O(n)
;空间复杂度:O(1)
;(k忽略不计)
代码如下:
void CreateNDate() { //写入n个数值 int n = 10000000; srand((unsigned int)time(NULL)); //以写的方式打开文件 const char* file = "data.txt"; FILE* pf = fopen(file, "w"); if (pf == NULL) { perror("fopen fail!"); return; } //写数据进入文件 for (int i = 0; i < n; i++) { int val = (rand() + i) % 10000000; fprintf(pf, "%d\n", val); } //关闭文件 fclose(pf); pf = NULL; } void TopK() { //以读的方式打开文件 const char* file = "data.txt"; FILE* pf = fopen(file, "r"); if (pf == NULL) { perror("fopen fail!"); return; } //开K个空间:为建小堆做准备 int k; printf("请输入要取的最大前k个数:"); scanf("%d", &k); int* kminheap = (int*)malloc(sizeof(int) * k); if (kminheap == NULL) { perror("malloc fail!"); return; } //读取文件中的前K个数据 for (int i = 0; i < k; i++) { fscanf(pf, "%d", &kminheap[i]); } //建K个数的小堆(向下调整算法) for (int i = (k - 1 - 1) / 2; i >= 0; i--) { AdjustDown(kminheap, k, i); } //取剩下的N-K个数与堆顶进行比较+向下调整 int val; while (fscanf(pf, "%d", &val) != EOF) { if (val > kminheap[0]) { kminheap[0] = val; AdjustDown(kminheap, k, 0); } } printf("最大的前%d个数:", k); for (int i = 0; i < k; i++) { printf("%d ", kminheap[i]); } printf("\n"); //关闭文件 fclose(pf); pf = NULL; } int main() { CreateNDate(); TopK(); return 0; }
假设降序:那是建小堆还是建大堆呢?
结论:
利用堆删除思想来进行排序:建堆和堆删除中都用到了向下调整
,因此掌握了向下调整,就可以完成堆排序。
假设6个数据建小堆:
void HeapSort(HPDataType* a, int n) { 向上调整算法建小堆:O(n*logn) //for (int i = 1; i < n; i++) //{ // AdjustUp(a, i); //} //向下调整算法建小堆:O(n) for (int i = (n - 1 - 1) / 2; i >= 0; i--) { AdjustDown(a, n, i); } //O(n*logn) int end = n - 1; while (end > 0) { Swap(&a[0], &a[end]); AdjustDown(a, end, 0); end--; } } int main() { int a[] = { 1,5,3,6,8,9,2,4,0,7 }; HeapSort(a, sizeof(a) / sizeof(a[0])); for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++) { printf("%d ", a[i]); } printf("\n"); }
堆排序时间复杂度计算:
重点理解
:向下调整算法。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。