堆的相关特点
一.建堆的两种方法
给定一个数组，其中数组里面的元素个数是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;
}运行结果：
原文地址：https://blog.csdn.net/lihaolihao111111/article/details/140532927
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！