作者：一个喜欢猫咪的的程序员
专栏：《数据结构》
喜欢的话：世间因为少年的挺身而出，而更加瑰丽。 ——《人民日报》
目录
堆排序：（以小堆为例）
堆的分类：
- 升序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高的次数，最多调整层数为：
F（h）=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*F（h）=2^1*（h-1）+2^2*(h-2)+2^3*(h-3)+...+2^(h-2)*2+2^(h-1)*1+2^(h)*0 ——②
有错位相减②-①可得：
F（h）=-2^0*（h-1）+2^1+2^2+....+2^(h-2)+2^(h-1)
F（h）=2^h-1-h ——③
当树高为h时，节点总个数N为：
N=2^0+2^1+...+2^（h-2）+2^（h-1）
N=2^h-1 ——④
有④可得：h=log（N+1） ——⑤
综合③④⑤可得：
F（N）=N-log（N+1）
- 因此时间复杂度为O（N）
向上调整具体的时间复杂度：
在一层，需要向上调整0次
第二层，向上调整1次
第三层，向上调整2次
...
第h-1层，向上调整h-2次
第h层，向上调整h-1次
F（h）=2^1*1+2^2*2+....+2^(h-1)*(h-1)。
由错位相减可得：
F(N)=2N(1-log(N+1))。
- 时间复杂度为O（N*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;
-
}
转载：https://blog.csdn.net/m0_69061857/article/details/128359186