堆的相关特点

一.建堆的两种方法

给定一个数组，其中数组里面的元素个数是n个如何能够把这个数组建立成为一个堆，今天探讨两种方法，分别是向上调整法和向下调整法，分别探讨他们的时间复杂度

向上调整法（以小堆为例）

回顾一下向上调整法

关于向上调整法，我们之前的具体思路是：比较父节点和子节点的大小，如果子节点比父节点小的话就交换两个的值

//交换两个数的值
void Swap(int* a, int* b)
{int temp = *a;*a = *b;*b = temp;
}
//向上调整算法
void AdjustUp(int* a, int n)
{int child = n;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;}}
}

那么如何运用上面的算法嘞

int main()
{int a[] = { 2,1,4,6,8,3,9};for (int i = 1; i < sizeof(a) / sizeof(a[0]); i++){AdjustUp(a, i);}for (int i = 0; i < sizeof(a)/sizeof(a[0]); i++){printf("%d ", a[i]);}return 0;
}

结果如下

通过画图，我们了解到该结果是正确的

时间复杂度

关于堆(设堆的高度为h)

第几层	节点数	每个节点向上调的次数
0	2^0	0
1	2^1	1
2	2^2	2
3	2^3	3
h-1	2^(h-1)	h-1

总共调的次数为

O（h）=2^1*1+2^2*2+2^3*3+……+2^(h-1)*(h-1)

两边同时乘以一个2

2O（h）= 2^2*1+2^3*2+2^4*3+……+2^h*(h-1)

上面两个式子相减得到

O（h）=-(2^1+2^2+2^3+……+2^(h-1))+2^h*(h-1)

根据等比数列的前n项和公式得到

O（h）=2^h*(h-2)+2

根据节点数和高度得关系：N=2^h-1 得到:h=log2(N+1)

O（N）=(N+1)[log2(N+1)-2]+2

所以向上调整法建堆的时间复杂度是

O（N）=N*log2(N)

向下调整法（以小堆为例）

思路：从倒数第一个非叶子开始（也就是倒数第二层），一直向下调

void AdjustDown(int* a, int n, int parent)
{int child = parent * 2 + 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;}}
}

int main()
{int a[] = { 2,1,4,6,8,3,9};int n = sizeof(a) / sizeof(a[0]);for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, n, i);}for (int i = 0; i < n; i++){printf("%d ", a[i]);}return 0;
}

时间复杂度

层数	节点	调整次数
1	2^0	h-1
2	2^1	h-2
3	2^2	h-3
4	2^3	h-4
h	2^(h-1)	0

所以：

O（h）=2^0*(h-1)+2^1*(h-2)+2^2*(h-3)+……+2^(h-2)*1

等式两边同时乘以一个2得到

2*O（h）= 2^1*(h-1)+2^2*(h-2)+……+2^(h-2)*2+2^(h-1)*1

两式相减得到

O（h）=1-h+2^1+2^2+……+2^(h-1)+2^0-2^0

化简得到 O(N)=N-log2(N+1)

所以向下调整法的时间复杂度为O（N）

堆排序（以升序为例）

给定一个数组，叫你如何排序嘞，这里我们运用建立堆的方式？

关于是建立大堆还是小堆

如果建立小堆的话，不便于后续的操作，这里我们建立一个大堆的方式

那么，如何通过一个大堆来实现数组的升序排序嘞？

比如下面的大堆，先交换数组首尾的值，交换之后不把最后一个元素看做堆里面的元素，继续向下调整，然后重复上面的步骤

int main()
{int a[] = { 46,23,40,35,27,29,30,24 };int n = sizeof(a) / sizeof(a[0]);for (int i = (n - 1 - 1) / 2; i >= 0; i--)   //时间复杂度O（N）{AdjustDown(a, n, i);}int end = n - 1;while (end >= 0)                             //时间复杂度O（N*logN）{Swap(&a[0], &a[end]);AdjustDown(a, end, 0);end--;}for (int i = 0; i < n; i++){printf("%d ", a[i]);}return 0;
}                                                       //总的时间复杂度O（N*logN）

堆的TOPK问题

场景：给定你一定量的数据，叫你找出最大的10个或者最小的10个数据，如果你用排序的方法来，当这个数据很大的时候，比如100亿，时间复杂度会很大

那么如何用堆的方法来选出前TOPK的数据

1.先建立一个有K个数据的小堆

2.后续的数据和堆顶的数据相比较，如果数据比堆顶的数据大的话，就代替堆顶的数据，这样留下来的数据就是最大的10个

void CreateNDate()
{// 造数据int n = 100000;srand(time(0));const char* file = "data.txt";FILE* fin = fopen(file, "w");if (fin == NULL){perror("fopen error");return;}for (int i = 0; i < n; ++i){int x = (rand() + i) % 1000000;fprintf(fin, "%d\n", x);}fclose(fin);
}void topk()
{printf("请输入k：>");int k = 0;scanf("%d", &k);const char* file = "data.txt";FILE* fout = fopen(file, "r");if (fout == NULL){perror("fopen error");return;}int val = 0;int* minheap = (int*)malloc(sizeof(int) * k);if (minheap == NULL){perror("malloc error");return;}for (int i = 0; i < k; i++){fscanf(fout, "%d", &minheap[i]);}// 建k个数据的小堆for (int i = (k - 1 - 1) / 2; i >= 0; i--){AdjustDown(minheap, k, i);}int x = 0;while (fscanf(fout, "%d", &x) != EOF){// 读取剩余数据，比堆顶的值大，就替换他进堆if (x > minheap[0]){minheap[0] = x;AdjustDown(minheap, k, 0);}}for (int i = 0; i < k; i++){printf("%d ", minheap[i]);}fclose(fout);}int main()
{CreateNDate();topk();return 0;
}

运行结果：