TOPK problem

One Problem description

topk The problem is n Before the number is selected k A big （ Small ） The number of （n>>k（n<<k））, Before election k Take a large number as an example

Two Ideas

1 Heap sort O（n*logn） But if n Very big words , There may not be so much space for heap sorting

2 Build a pile After selecting the data at the top of the heap every time, continue to build the heap for the remaining data , Until the screening is complete n A digital . Time complexity

O（n+logn*k） Time efficiency is relatively 1 better . But build n The space required for a number of heaps may be very large .

3 Yes n The first of the numbers k First build a small pile of numbers , And then we'll talk to n-k The data were compared , If this number is larger than the data at the top of the heap , Then go into the pile , Then the small pile discharged is the front k A small pile of big numbers , Then we'll do a heap sort , You can select the front k Big numbers . Time complexity O（k+logk*（n-k））

Compared with 2 The time complexity has not changed much , The real optimization is in space .

Code implementation ：

#define _CRT_SECURE_NO_WARNINGS 1 
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>


void print(int* pa, int sz)
{
	assert(pa);
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%d ", pa[i]);
	}
	printf("\n");
}

void swap(int* pa1, int* pa2)
{
	int tmp = *pa1;
	*pa1 = *pa2;
	*pa2 = tmp;
}

void AdjustDown(int* pa, int size, int parent)
{
	assert(pa);
	int child = parent * 2 + 1;// The default is left child , Then take out the smaller one of the left and right children 
	while (child < size)
	{
		if (pa[child + 1] > pa[child] && child + 1 < size)// If the right child is older than the left child , Then the child +1, Default to older children , Don't care about children , Only care about the relatively larger one   And only the right child can 
		{
			child = child + 1;
		}// Find younger children 

		if (pa[child] > pa[parent])
		{
			swap(&pa[child], &pa[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void Adjustup(int* pa, int child)
{
	assert(pa);
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (pa[child] > pa[parent])
		{
			swap(&pa[child], &pa[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}


void HeapDownSort(int* pa, int size)
{
	assert(pa);

	int i = 0;
	for (i = (size - 1 - 1) / 2; i >= 0; i--)//size-1 Is the subscript of the last node , Then his parent node is (size-1-1)/2
	{
		AdjustDown(pa, size, i);
	}// Pile up 

	for (i = 1; i <= size - 1; i++)
	{
		swap(&pa[0], &pa[size - i]);
		AdjustDown(pa, size - i, 0);
	}
}

void topk(int*pa,int sz,int k)
{
	int i = 0;
	for (i = 0; i < k; i++)
	{
		Adjustup(pa, i);
	}// Before formation k A heap of numbers 

	for (i = k; i < sz; i++)
	{
		if (pa[k] > pa[0])
		{
			swap(&pa[k], &pa[0]);
			AdjustDown(pa, k, 0);
		}// If the subsequent number is larger than the data at the top of the heap , After exchanging them for so long, they adjusted downward , Can form before k There are a lot of the largest numbers 
	}

	HeapDownSort(pa, sz);
}

int main()
{
	int a[] = { 1,2,3,4,5,6,7,8,9,10 };
	int k = 5;
	int sz = sizeof(a) / sizeof(a[0]);

	topk(a, sz,k);

	for (int i = 0; i < k; i++)
	{
		printf("%d ", a[i]);
	}
	
}