4

堆排序+TOPK问题_萌新的日常的技术博客_51CTO博客

 1 year ago
source link: https://blog.51cto.com/u_15787387/5881182
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

一.堆排序

1.使用向上还是向下调整建堆好？

(1)向上调整算法建堆的时间复杂度

void adjustup(HPDatatype* a, int child)//向上调整算法
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[parent] < a[child])//以大堆为例
		{
			swap(&a[parent], &a[child]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

1. 完整过程

堆排序+TOPK问题_时间复杂度

由于第一层不需要调整，所以从第二层开始 这里没有详细算，因为我们发现在最后的2^(h-1)*(h-1) 用公式拆分后，就可以算出结果
通过大O的渐进表示法， 时间复杂度为O(N * logN)

(2)向下调整算法建堆的时间复杂度

void adjustdown(HPDatatype* a, int parent,int size)//向下调整算法
{
	int child = parent * 2 + 1;//假设为左孩子
	while (child<size)
	{
		if (child+1<size&&a[child] < a[child + 1])//如果假设不成立，就为右孩子
		{
			child++;
		}
		if (a[parent] < a[child])//孩子大于父亲
		{
			swap(&a[parent], &a[child]);
			parent = child;
			child=parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

1.完整过程

堆排序+TOPK问题_#include_02
  • 由于2^h-1为二叉树总节点个数，所以最后一层为h-1, 但因向下调整算法是从倒数第二层的父节点开始的即 从h-2层开始，
  • 这里不太懂为什么从倒数第二层的父亲节点开始 可以看： 堆的带图详解
堆排序+TOPK问题_数据_03
  • 由于大O的渐进表示法，可以把时间复杂度看作为O(N)

(3)总结

  • 因为 向上调整算法的时间复杂度为O(NlogN) ，而向下调整算法的时间复杂度为 O(N)
  • 所以使用向下调整算法建堆更好

2. 排升序

(1) 建小堆

堆排序+TOPK问题_数据_04
  • 假设小堆如图所示
堆排序+TOPK问题_#include_05

  • 只能取到最小的节点，再次想要取次小的节点时会打乱节点之间的结构，从而需要重新建堆

  • 而重新建堆的时间复杂度为O(N)，遍历一次数组的时间复杂度也为O(N)，没有效率

(2) 建大堆

堆排序+TOPK问题_时间复杂度_06
  • 假设为大堆所图所示
    堆排序+TOPK问题_数据_07

交换最大的节点与最后一个节点，此时左子树与右子树结构没有发生变化 当从最后一个节点到第二层完成交换时，
共操作了 2^h 次 ，N=2^h ，h=log N
即时间复杂度为O(logN)

3. 堆排序时间复杂度统计

在整体过程中，主要有 向下调整算法建堆 及 排序组成
向下调整算法建堆的时间复杂度为O(N)
排序的时间复杂度为O(logN)
即堆排序的时间复杂度为O(NlogN)

4.完整代码

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

void swap(int * s1, int * s2)
{
int tmp = 0;
tmp = *s1;
*s1 = *s2;
*s2 = tmp;
}
void adjustdown(int * a, int parent, int size)//向下调整算法
{
int child = parent * 2 + 1;//假设为左孩子
while (child < size)
{
if (child + 1 < size && a[child] < a[child + 1])//如果假设不成立，就为右孩子
{
child++;
}
if (a[parent] < a[child])//孩子大于父亲
{
swap(&a[parent], &a[child]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void print(int* a, int n)
{
int i = 0;
for (i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
}
void heapsort(int* a, int n)//堆排序——升序
{
int i = 0;
for (i = (n - 1 - 1) / 2; i >= 0; i--)//使用向下调整算法 时间复杂度为O(N)
{
adjustdown(a, i, n);
}

int end = n - 1;//排升序，建大堆 时间复杂度为O(logN)
while (end > 0)//end作为下标当为0时，说明只剩下一个数，不需要调整
{
swap(&a[0], &a[end]);//交换最大的数与最后一个数的位置，并将前n-1个数再次向下调整
adjustdown(a, 0, end);//此时end作为整体调整的个数
end--;
}
}
int main()
{
int arr[] = { 27,15,19,18,28,34,65,49,25,37 };
int n = sizeof(arr) / sizeof(arr[0]);
heapsort(arr, n);
print(arr, n);

return 0;
}

二 、 TOPK问题

即求数据结合中前k个最大的元素或者最小的元素，一般情况下数据量比较大

2.两种方法

建立一个N个数的大堆，删除k次，依次取堆顶
这种方法我们在上一篇实现过，若想看点击： 堆的带图详解

假设N很大，k很小，比如N=100亿 k=10
1G=1024 * 1024 * 1024Byte 约等于 10亿Byte
100 亿个整数 则需要 40G空间，
正常来说我们把数据放入内存中，再用堆去实现，但若数据太大，内存存不下,直接在磁盘文件中，就不会能在建堆了
40G属于数据太大的情况，所以不能进入内存中

建立k个数小堆，依次遍历数据，比堆顶的数据大，就进行交换，再向下调整，最后最大的k个数就在小堆中

堆排序+TOPK问题_数据_08

假设共有如上的数据，n =6 ，k=3

堆排序+TOPK问题_数据_09
  • 取前k个数据建立一个小堆
堆排序+TOPK问题_数据_10

再取剩余的数据依次与其比较，若比堆顶数据大，则赋值，同时进行向下调整，使堆顶为最小的数

3.完整代码

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
void swap(int* s1, int* s2)
{
int tmp = 0;
tmp = *s1;
*s1 = *s2;
*s2 = tmp;
}
void adjustdown(int* a, int parent, int size)//向下调整算法 这里以小堆为例
{
int child = parent * 2 + 1;//假设为左孩子
while (child < size)
{
if (child + 1 < size && a[child] > a[child + 1])//如果假设不成立，就为右孩子
{
child++;
}
if (a[parent] > a[child])//孩子小于父亲  
{
swap(&a[parent], &a[child]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
int main()
{
int n = 0;
int k = 0;
printf("请输入数字:>");
scanf("%d%d", &n, &k);
FILE* pf = fopen("qwe.txt", "w");
if (pf == NULL)
{
perror("fopen tail");
exit(-1);
}
int i = 0;
srand(time(0));
for (i = 0; i < n; i++)//将n个数据传入文件中
{
int ret = rand();
fprintf(pf, "%d\n", ret);
}
fclose(pf);//输入文件数据后就关闭
//////////////////////////////////////////
FILE* cout = fopen("qwe.txt", "r");
if (cout == NULL)
{
perror("fopen tail");
exit(-1);
}
int* minheap = (int*)malloc(sizeof(int) * k);
if (minheap == NULL)
{
perror(" malloc fail");
}

for (i = 0; i < k; i++)//将k个数据传入数组中 即使用k个数建堆
{
fscanf(cout, "%d", &minheap[i]);
}

for (i = (k - 1 - 1) / 2; i >= 0; i--)//使用向下调算法建小堆
{
adjustdown(minheap, i, k);
}

int val = 0;
while (fscanf(cout, "%d", &val)!=EOF)//将文件剩余的数据继续传入数组中比较
{
if (val > minheap[0])//如果val值比堆顶数据大
{
minheap[0] = val;
adjustdown(minheap, 0, k);//向下调整再次找到最小的堆顶
}
}



for (i = 0; i < k; i++)
{
printf("%d ", minheap[i]);
}
fclose(cout);
cout = NULL;
return 0;
}

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK