堆中的时间复杂度+TOP K问题
堆中的时间复杂度分析
回顾: 堆在物理上:数组 逻辑上:完全二叉树
1.堆排序是什么?
// 排升序
void HeapSort(int* a, int n)
{
// 建大堆 -
for (int i = (n - 1 - 1) / 2; i >= 0; --i)
{
AdjustDown(a, n, i);
}
int end = n - 1;
while (end > 0)
{
Swap(&a[0], &a[end]);
// 选出次大的
AdjustDown(a, end, 0);
--end;
}
}
2.堆的接口实现回顾
typedef int HPDataType;
typedef struct Heap
{
//数组
HPDataType*a;
int size;
int capacity;
};
void HeapInit(HP* php)
{
assert(php);
php->a=NULL;
php->size=php->capacity=0;
}
// 堆的销毁
void HeapDestory(Heap* hp)
{
assert(php);
free(php->a);
php->a=NULL;
php->size=php->capacity=0;
}
// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{
assert(php);
//涉及到有没有空间插入
if(php->size==php->capacity)
{
int newcapacity=php->capacity==0?4:php->capacity*2;//原来就没空间先给4个,空间不够直接扩2倍
HPDataType*tmp=(HPDataType*)realloc(php->a,newcapacity*sizeof(HPDataType));
}
if(tmp==NULL)
{
perror("realloc fail");
return;
}
//忘了 扩完容重新赋值啊
php->a=tmp;
php->capacity=newcapacity;
//插到尾
php->a[php->size]=x;//不是插在size-1 是插在size-1的后面
php->size++;
//破坏了原来的大小关系,通过向上调整法
Adjustup(php->a,php->size);
}
void Adjustup(HPDataType*a,int child)//谁小谁当爹
{
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;
}
}
void Swap(HPDataType*p1,HPDataType*p2)
{
HPDataType tmp=*p1;//这个是代表的p1解引用,所以tmp无需*
*p1=*p2;
*p2=tmp;
}
// 堆的删除
void HeapPop(Heap* hp)
{
//顶和尾互换后删掉尾,删尾很简单直接--
assert(php);
assert(php->size>0);
Swap(&php->a[0],&php->a[php->size-1]);
php->size--;
//向下调整会原来的堆
Adjustdown(php->a,php->size,0);//从头开始向下调整
}
void Adjustdown(HPDataType*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;
}
}
// 取堆顶的数据
HPDataType HeapTop(Heap* hp)
{
assert(php);
assert(php->size>0);//堆不为空,有东西可取
return php->a[0];
}
// 堆的数据个数
int HeapSize(Heap* hp)
{
assert(php);
assert(php->size>0);
return php->size;
}
// 堆的判空
bool HeapEmpty(Heap* hp)
{
assert(php);
return php->size==0;
}
完全二叉树的高度范围
最多:满二叉树 最后一层是满的 h=log(N+1)
最少: 最后一层只有一个 h=logN+1
所以无论是完全二叉树还是满二叉树
高度的量级都是logN
所以时间复杂度都是O(logN)
堆排序有两种:向上调整建堆 向下调整建堆 我们通常用向下建堆
这里详细讲一下,为什么是向下调整建堆
向下调整建堆是从哪里开始调的?
从最后一个分支节点,–调
首先:最后一层的叶子结点是不需要调的
这里的时间复杂度不是看代码就能看出来的,需要找规律列式子算出来
最终得到向下调整建堆时间复杂度是:O(N)
Top K问题
在N个数据中找到最大的前K个
其中
若N和K相差不多就使用方法一
若N>>>K就是用方法二
方法一:建一个N个数的大堆 O(N)
Pop K次 O(K*logN)
取一个删一个,取出最大的K个
但是这个方法有个缺陷
若N>>>K,比如 N=10亿+
让我们来算算他所需要的空间
1G=1024MB=1024 x 1024KB=1024 x 1024 x 1024Byte
若有10亿个数据 大概需要3.8个G
这个数组的空间太大 是开辟不出来的
所以当N>>>K我们需要
方法二:
用前K个数,建小堆 O(K)
剩下的数据与堆顶的数据比较,比堆顶大就代替顶进堆,覆盖根再向下调整
O(logK*(N-K))
数字 int 一个4个字节
所以这个方法只需要4K个字节
最后这个小堆的K个数,就是最大的前K个数
合计复杂度:O(N)
#include<stdio.h>
#include<stdlib.h>
void CreatNData()
{
//造数据函数
int n = 100000;
srand(time(0));
const char* file = "data.txt";
FILE* fin = fopen(file, "w");
if (fin == NULL)
{
perror("fopen fail");
reutrn NULL;
}
for (int i = 0; i < n; i++)
{
int x = (rand() + i) % 100000;//因为rand只能做到三万个随机数据不重复,+i可以大大减少重复率
fprintf(fin, "%d\n", x);
}
fclose(fin);
}
int main()
{
int k;
scanf("%d", &k);
int* kminheap(int*)malloc(sizeof(int) * k);//因为k是我们手动输入的所以只能用malloc
if (kminheap == NULL)
{
perror("malloc fail");
return NULL;
}
const char* file = "data.txt";
FILE* fout = fopen(file, "r");
if (fout == NULL)
{
perror("fopen fail");
reutrn NULL;
}
for (int i = 0; i < k; i++)//读取前K个数
{
fscanf(fout, "%d\n", &kminheap[i]);
}
//建K个数的小堆
for (int i = (k - 1 - 1) / 2; i >= 0; i--)
{
Adjustdown(kminheap, k, i);
}
int x = 0;
while (fscanf(fout, "%d", &kminheap[i]));
{
if (x > kminheap[0])//大于堆顶
{
kminheap[0] = x;//f覆盖
Adjustdown(kminheap, k, 0);
}
}
printf("打印最大的前%d个", k);
for (int i = 0; i < k; i++)
{
printf("%d", kminheap[i]);
}
printf("\n");
return 0;
}
原文地址：https://blog.csdn.net/2301_81256732/article/details/143667462
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！