【数据结构】堆（二）——堆排序、TOP-K问题
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
作者一个喜欢猫咪的的程序员
专栏《数据结构》
喜欢的话世间因为少年的挺身而出而更加瑰丽。 ——《人民日报》
目录
堆排序以小堆为例
堆的分类
- 升序or降序
- 大堆or小堆
void test2()
{//堆排序
int array[] = { 27,15,19,18,28,34,65,49,25,37 };
Heapsort(array, sizeof(array) / sizeof(array[0]));
for (int i = 0; i < sizeof(array) / sizeof(array[0]); i++)
{
printf("%d ", array[i]);
}
printf("\n");
}Heapsort函数堆排序
int array[] = { 27,15,19,18,28,34,65,49,25,37 };
需将这个数组进行大堆排列分为两种调整形式向上调整和向下调整。
向上调整和向下调整的思想可以参考我的例外一篇博客http://t.csdn.cn/YFSpd
void Ajustup(HPDataType*a, int child)
{//N*logN
assert(a);
//int child = n - 1;
while (child > 0)
{
int parent = (child - 1) / 2;
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);
child = parent;
}
else
{
break;
}
}
}
void Ajustdown(HPDataType* a, int n,int parent)
{//O(N)
assert(a);
int child = 2 * parent+1;
while (child<n)
{
if (child + 1 < n && a[child] < a[child + 1])// <假设左子树大
{
child++;
}
if (a[child] > a[parent])//>大堆<为小堆
{
Swap(&a[child], &a[parent]);
parent = child;
child = child * 2 + 1;
}
else
{
break;
}
}
}向上调整和向下调整具体的时间复杂度是多少呢
向下调整具体的时间复杂度
假设树高为h
第h层有2^(h-1个节点需要向下调整0次直接不算从第h-1层开始算。
第h-1层有2^h-2个节点需要向下调整1层。
第h-2层有2^h-3个节点需要向下调整2层。
......
第4层有2^3个节点需要向下调整h-4层。
第3层有2^2个节点需要向下调整h-3层。
第2层有2^1个节点需要向下调整h-2层。
第1层有2^0个节点需要向下调整h-1层。
当h高的次数最多调整层数为
Fh=2^0*h-1+2^1*(h-2)+2^2*(h-3)+...+2^(h-3)*2+2^(h-2)*1+2^(h-1)*0 ——①
2*Fh=2^1*h-1+2^2*(h-2)+2^3*(h-3)+...+2^(h-2)*2+2^(h-1)*1+2^(h)*0 ——②
有错位相减②-①可得
Fh=-2^0*h-1+2^1+2^2+....+2^(h-2)+2^(h-1)
Fh=2^h-1-h ——③
当树高为h时节点总个数N为
N=2^0+2^1+...+2^h-2+2^h-1
N=2^h-1 ——④
有④可得h=logN+1 ——⑤
综合③④⑤可得
FN=N-logN+1
- 因此时间复杂度为ON
向上调整具体的时间复杂度
在一层需要向上调整0次
第二层向上调整1次
第三层向上调整2次
...
第h-1层向上调整h-2次
第h层向上调整h-1次
Fh=2^1*1+2^2*2+....+2^(h-1)*(h-1)。
由错位相减可得
F(N)=2N(1-log(N+1))。
- 时间复杂度为ON*logN
如何实现堆排序
显然向下调整优于向上调整。
先利用Ajustdown排序好数组然后再用交换Ajustdown实现小堆。
void Heapsort(int*a,int n)//堆排序
{//向上调整
for (int i = 1; i <n; i++)
{
Ajustup(a, i);
}
//向下调整
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
Ajustdown(a, n, i);
}
int end = n - 1;
while (end>0)
{
Swap(&a[0], &a[end]);
Ajustdown(a, end, 0);
end--;
}
//N*logN
}
void test2()
{//堆排序
int array[] = { 27,15,19,18,28,34,65,49,25,37 };
Heapsort(array, sizeof(array) / sizeof(array[0]));
for (int i = 0; i < sizeof(array) / sizeof(array[0]); i++)
{
printf("%d ", array[i]);
}
printf("\n");
}TOP-K问题
TOP-K问题即求数据结合中前K个最大的元素或者最小的元素一般情况下数据量都比较大。
比如专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
当数据量特别大时我们造一个数组来存储他们依次存储时就不大现实。
可以先开一个K个空间的数组将这个数据量的前K个放进去将他们小堆排列并将这个数据量每个数与堆顶的元素相比较比它大就替代它进入数组在向下排列以此循环。
void test3()
{
int minHeap[5];
FILE* fout = fopen("data.txt", "r");
if (fout == NULL)
{
perror("fopen fail");
exit(-1);
}
int k = sizeof(minHeap) / sizeof(minHeap[0]);
for (int i = 0; i < k; i++)
{
fscanf(fout,"%d",&minHeap[i]);
}
for (int i = 0; i < sizeof(minHeap) / sizeof(minHeap[0]); i++)
{//检查是否录入数据
printf("%d ", minHeap[i]);
}
printf("\n");
for (int i = (k - 1 - 1) / 2; i >= 0; i--)
{
Ajustdown(minHeap, k, i);
}
for (int i = 0; i < sizeof(minHeap) / sizeof(minHeap[0]); i++)
{//检查是否为大小堆
printf("%d ", minHeap[i]);
}
printf("\n");
int data = 0;
while (fscanf(fout, "%d", &data) != EOF)
{
if (data > minHeap[0])
{
minHeap[0] = data;
Ajustdown(minHeap, k, 0);
}
}
int end = k - 1;
while (end > 0)
{
Swap(&minHeap[0], &minHeap[end]);
Ajustdown(minHeap, end, 0);
end--;
}//完成升序或者降序
for (int i = 0; i < sizeof(minHeap) / sizeof(minHeap[0]); i++)
{//检查是否为大小堆
printf("%d ", minHeap[i]);
}
printf("\n");
fclose(fout);
}
void test4()
{
int n, k;
scanf("%d %d", &n, &k);
FILE* fint = fopen("data1.txt", "w");
if (fint == NULL)
{
perror("fopen fail");
exit(-1);
}
srand(time(0));
int randK = k;
for (size_t i = 0; i < n; ++i)
{
int data = rand() % 100000;
fprintf(fint, "%d\n", data);
}
fclose(fint);
int* minHeap = (int*)malloc(sizeof(int) * k);
FILE* fout = fopen("data1.txt", "r");
if (fout == NULL)
{
perror("fopen fail");
exit(-1);
}
for (int i = 0; i < k; i++)
{
fscanf(fout, "%d", &minHeap[i]);
}
for (int i = 0; i < k; i++)
{//检查是否录入数据
printf("%d ", minHeap[i]);
}
printf("\n");
for (int i = (k - 1 - 1) / 2; i >= 0; i--)
{
Ajustdown(minHeap, k, i);
}
for (int i = 0; i < k; i++)
{//检查是否为大小堆
printf("%d ", minHeap[i]);
}
printf("\n");
int data = 0;
while (fscanf(fout, "%d", &data) != EOF)
{
if (data > minHeap[0])
{
minHeap[0] = data;
Ajustdown(minHeap, k, 0);
}
}
int end = k - 1;
while (end > 0)
{
Swap(&minHeap[0], &minHeap[end]);
Ajustdown(minHeap, end, 0);
end--;
}//完成升序或者降序
for (int i = 0; i < k; i++)
{//检查是否为大小堆升序或者降序
printf("%d ", minHeap[i]);
}
printf("\n");
fclose(fout);
}
int main()
{
//test1();
test2();
//test3();
//test4();
return 0;
}