堆--TopK问题

题目要求：

输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

示例 1：

输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]

示例 2：

输入：arr = [0,1,2,1], k = 1
输出：[0]

思路一：

先降序排序，排序结束后前10个就是最小的。时间复杂度为O(N*logN)

一个结点的向下调整时间复杂度只与树的高度有关。时间复杂度为O(logN)

降序排序最坏情况下需要对每一个结点都进行排序

思路二：

将N个数依次插入一个小堆，也就是将N个数字全部保存在一个小堆中。

PopK次，每次取堆顶的数据删除，并且由于是最小堆，所以每次删除的数字都是堆中最小的数字。

记录不断选出前K个最小

将N个数字依次插入大堆中的时间复杂度为O(N)；Popk次的时间复杂度为O(k*logN)。所以思路二的时间复杂度为：O(N+k*logN)

思路二的时间复杂度看起来比思路一的时间复杂度更高，然而实际上一般情况下k远小于N，所以一般情况下思路二时间复杂度更优

思路三：

如果N过大，比如N为数亿次，内存中无法存储大量的数据，那么前两种思路也就不可行了

①用前k个数建立一个k个数的大堆②剩下的N-k个数，依次跟堆顶的数据进行比较。如果比堆顶的数据小，那么就顶替堆顶数据，在向下调整大堆③最终堆里面的k个数就是最小的k个数

因为是最大堆，所以堆顶的数据一定是堆中最大的数据，这样就可以保证每次都与堆中最大的对比，从而保留较小值

时间复杂度：O(K+(N-K)*logK)

代码实现：

 
 
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
 #pragma
#include
#include
#include
#include
 
typedef int HPDataType;
typedef struct heap
{
	int* a;
	int size;
	int capacity;
}HP;
 
void HeapPrintf(HP* hp);//循环输出打印堆中元素
void Swap(HPDataType* px,HPDataType *py);
void AdjustUp(int* a, int size, int child);//向上调整
void AdjustDown(int* a,int size,int parent);//向下调整
void HeapInit(HP* hp);
void HeapDestory(HP* hp);
void HeapPush(HP* hp,HPDataType x);
void HeapPop(HP* hp);//删除堆顶数据
HPDataType HeapTop(HP* hp);//获取堆顶数据
int HeapSize(HP* hp);
bool HeapEmpty(HP* hp);
 
 
void Swap(HPDataType* px,HPDataType* py)
{
	HPDataType* tmp = *px;
	*px = *py;
	*py = tmp;
}
 
void HeapInit(HP* hp)
{
	assert(hp);
	hp->a = NULL;
	hp->size = hp->capacity = 0;
}
 
 
void HeapDestory(HP* hp)
{
	assert(hp);
	free(hp->a);
	hp->a = NULL;
	hp->size = hp->capacity = 0;
}
 
//向上调整
//n为数组大小，child为新插入的数据位置
void AdjustUp(int *a,int size,int child)
{
	assert(a);
	int parent = (child - 1) / 2;
	while (child>0)
	{
		//大堆
		if (a[child] > a[parent])
		//小堆
		//if(a[child]
		{
			//父子数值交换
			Swap(&a[child], &a[parent]);
 
			//更新父子结点
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
 
//堆插入数据堆其他结点没有影响
//可能会影响它到根节点的路径上的结点关系
void HeapPush(HP* hp, HPDataType x)
{
	assert(hp);
	if (hp->size==hp->capacity)
	{
		int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
		HPDataType* tmp = realloc(hp->a, sizeof(HPDataType) * newcapacity);
		if (tmp==NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		hp->a = tmp;
		hp->capacity = newcapacity;
	}
	hp->a[hp->size] = x;
	hp->size++;
	AdjustUp(hp->a, hp->size, hp->size - 1);
}
 
 
void AdjustDown(int *a,int size,int parent)
{
	assert(a);
	int child = parent * 2 + 1;//左孩子
	while (child
	{
		//选更大的孩子结点，child+1为右孩子
		if (child+11]>a[child])
		//选更小的孩子节点
		//if(child+1
		{
			child++;//如果右孩子值更大/小，那么child指向右孩子
		}
		//大堆：如果大的孩子大于父亲则交换
		if (a[child]>a[parent])
		//小堆，如果小的孩子小于父亲则交换
		//if(a[child]
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
 
 
void HeapPop(HP* hp)
{
	assert(hp);
	assert(hp->size > 0);
	Swap(&hp->a[0], &hp->a[hp->size - 1]);//将堆顶数据与数组中最后一个数据交换
	hp->size--;//删除数组中的最后一个数据
	AdjustDown(hp->a, hp->size,0);//传入数组，数组的大小，向下调整起始位置
}
 
void HeapPrintf(HP* hp)
{
	for(int i=0;isize;i++)
	{
		printf("%d ",hp->a[i]);
	}
	printf("\n");
}
 
HPDataType HeapTop(HP* hp)
{
	assert(hp);
	assert(!HeapEmpty(hp));
	return hp->a[0];
}
 
int HeapSize(HP* hp)
{
	return hp->size;
}
 
bool HeapEmpty(HP* hp)
{
	assert(hp);
	return hp->size == 0;
}
 
int* getLeastNumbers(int* arr, int arrSize, int k, int* returnSize)
{    
    if(k==0||arrSize==0)
    {
        *returnSize=0;
        return NULL;
    }
    else
    {
        *returnSize=k;
    }
    HP hp;
    HeapInit(&hp);
 
    for(int i=0;i
    {
        HeapPush(&hp,arr[i]);
    }
    for(int i=k;i
    {
        if(arr[i]<HeapTop(&hp))
        {
            HeapPop(&hp);
            HeapPush(&hp,arr[i]);
        }
    }
    int* ret = (int*)calloc(k, sizeof(int));
    for (int i = 0; i < k; i++) 
    {
        ret[i] = HeapTop(&hp);
        HeapPop(&hp);
    }
    return ret;
 
}