“This is the 20th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

Topk

Find the largest first K of n numbers or find the smallest first K of n numbers

(n > K)

Find the top ten largest numbers out of 1000

Method 1:

The first ten are the largest in descending order. Time complexity O(N*log 2 N)

Method 2:

N values are inserted into the heap, PopK times, and the top K values are taken each time. Time complexity O(N+log 2 N)

Method 3:

Let’s say N is really big, N is a billion, there’s no memory for these numbers, they’re stored in a file, k is 100. Then neither method 1 nor method 2 can be used. Time complexity O(K+(n-k)log 2 K)

A billion integers and let’s see how much space it takes

1. Create a small heap of K numbers with the first K numbers

2. Compare the remaining N-k numbers with the data on the top of the heap. If the data is larger than the data on the top of the heap, replace the data on the top of the heap and adjust downward

3. The last K number in the heap is the largest K number

Topk print function TopkPrint

void TopkPrint(int* a, int n, int k)
{
	// Create a heap
	HP hp;
	// Initialize the heap
	HeapInit(&hp);
	// create a small heap with the first K numbers
	int i = 0;
	for (i = 0; i < k; i++)
	{
		HeapPush(&hp,a[i]);
	}
	// Compare the remaining n-k numbers with the top of the heap. If the number is larger than the top of the heap, replace the top of the heap and adjust downward
	// Replace to break the structure, we use the interface to implement, find the first pop, then push the large number of lines
	for (i = k; i < n ; i++)
	{
		// The top of the heap is less than the number in the array
		if (HeapTop(&hp) < a[i])
		{
			// Start with the top of the heap
			HeapPop(&hp);
			// Insert the number in the array into the heapHeapPush(&hp, a[i]); }}// Then print the heap
	HeapPrint(&hp);
	HeapDestroy(&hp);
}
Copy the code

For unmodified interfaces, seeAlgorithm for small size farmers stack horcruxes – blood and tenderness

Changed interface

Upadjustment function

// Adjust the function up
void AdjustUp(HPDataType* a, int size, int child)
{
	assert(a);
	int parent = (child - 1) / 2;
#if HEAP
	while (child > 0)
	{
		if (a[parent] < a[child])// If the father is smaller than the child, swap (heap)
		{
			Swap(&a[parent], &a[child]);
			// Call the child and father again after the exchange
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break; }}#elif! HEAP
	while (child > 0)
	{
		if (a[parent] > a[child])// If the father is bigger than the child, swap (small heap)
		{
			Swap(&a[parent], &a[child]);
			// Call the child and father again after the exchange
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break; }}#endif // HEAP
}

Copy the code

Downward adjustment function

// Adjust the function downward
void AdjustDown(HPDataType* a, int size, int parent)
{
	assert(a);
	// Create a child variable. If there are two children, add 1 to this variable
	int child = parent * 2 + 1;
#if HEAP
	while (child < size)
	{
		// Select the older child
		if (child + 1 < size && a[child] < a[child + 1])
		{
			child++;
		}
		// If the older child is still older than the father, switch
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break; }}#elif! HEAP
	while (child < size)
	{
		// Select a child
		if (child + 1 < size && a[child] > a[child + 1])
		{
			child++;
		}
		// If the child is younger than the father, the child should be exchanged
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break; }}#endif // HEAP	
}
Copy the code

Then add it to the heap.h file

0 Heap mode 1 Small heap mode
#define HEAP   0       
Copy the code