Binary tree (III) -- heap sort optimization, top k problem

One 、 Heap sort optimization        

In the previous lecture, we used to build small piles independently , Then put all the array elements into a small heap , Finally, pop up all elements from the small heap to sort the heap , Yes O（NlogN） Time complexity of , But the space complexity is O（N）, Worth optimizing .

The idea of optimizing heap sorting is as follows （ Take ascending order ）：

// Downward adjustment for a lot 
void AdjustDown(HPDataType* a,size_t size,size_t root)
{
	size_t parent = root;
	size_t child = parent * 2 + 1;
	while (child < size)
	{
		// First step ： Choose the older of the left and right children 
		if (child + 1 < size && a[child + 1] > a[child])
		{
			child++;
		}
		// If the child is bigger than the father, exchange , And continue to adjust down 
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

Let's review the deletion of elements in the pile （ The number of elements in the heap is N, Array implementation ）：

First deletion , The largest element is located at the root node （a[0]）, With the first a[N-1] In exchange for , Right again a[0] Downward adjustments .

Delete for the second time , The second element is located at the root node （a[0]）, With the first a[N-2] In exchange for , Right again a[0] Downward adjustments .

······

in other words , In the pile k Delete times , It can guarantee the number of k Big numbers are put in the right place （ Ascending sort ）.

This method also utilizes the idea of downsizing .

Specific code ：

void HeapSort(HPDataType* a, size_t n)
{
	// Ascending sort , It is inconvenient to operate after building a small pile , It's better to bubble directly 
	// There are two ways to build a reactor 
	// One is to build a heap with the idea of adjusting the inserted data upward 
	// First step ： Build a heap on the basis of the original array 
	int i = 0;
	/*for (i = 1; i < n; i++)
	{
		AdjustUp(a, i);
	}*/
	// Be careful ： Direct downward adjustment cannot build a heap , Downward adjustment requirements ： The left and right trees are small piles / It's all piles 
	// Build the heap with downward adjustment , It should be the last one internal vertex Start , Adjust upside down 
	// The penultimate space internal vertice, That's the last leaf Parent node 
	for (i = (n - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n,i);
	}
	//① Heap sort （ Ascending ） Using the idea of reducing scale ：
	// Choose the maximum number for the first time , Then scale down to n-1......
	//② The essence of heap sorting is selective sorting 
	// Using the structure of the heap i The second election i Large number 
	size_t end = n - 1;
	while (end>0  )
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		end--;
	}
}

int main()
{
	TestHeap();
	HPDataType a[] = { 4,2,7,8,5,1,0,6 };
	HeapSort(a, sizeof(a) / sizeof(HPDataType));
	for (size_t i = 0; i <= 7; i++)
		printf("%d ", a[i]);
	return 0;
}

The complete code file is as follows ：

Heap.h

#pragma once
#include<stdlib.h>
#include<assert.h>
#include<stdio.h>
#include<stdbool.h>

typedef int HPDataType;
typedef struct Heap {
	HPDataType* a;// The dynamic array 
	size_t size;// Data volume 
	size_t capacity;// Capacity 
}HP;
void Swap(HPDataType* pa, HPDataType* pb);
void HeapInit(HP* php);
void HeapDesTroy(HP* php);
void HeapPush(HP* php, HPDataType x);
void HeapPop(HP* php);
void HeapPrint(HP* php);
HPDataType HeapTop(HP* php);
size_t HeapSize(HP* php);
bool HeapEmpty(HP* php);
void AdjustUp(HPDataType* a, size_t child);
void AdjustDown(HPDataType* a, size_t size, size_t root);

Heap.c

#include"Heap.h"
void HeapInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->size = php->capacity = 0;
}
void HeapDesTroy(HP* php)
{
	assert(php);
	free(php->a);
	php->a = NULL;// Don't neglect this step 
	php->size = php->capacity = 0;
}

void Swap(HPDataType* pa, HPDataType* pb)
{
	HPDataType tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}

// The idea of algorithmic logic is binary tree , The physical operation is the data in the array 
// Upward adjustment for small piles 
void AdjustUp(HPDataType* a,size_t child)
{
	// Calculation formula of parent-child relationship （ about leftchild and rightchild All set up ）
	size_t parent = (child - 1) / 2;
	// May continue to rise 
	// Here is a small pile , If you need a lot , Only adjust if Just use the symbol in 
	while (child>0)
	{
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			// Update the relationship 
			child = parent;
			parent = (child - 1) / 2;
			// Be careful child=0 when ,parent=0, Will fall into a dead cycle .
			// Don't use it size_t,parent Never less than 0
			//-1/2==0
		}
		// We should also consider the situation of stopping in the middle 
		else
		{
			break;
		}
	}
}


// After inserting new data , Keep a big pile 、 The nature of small root pile 
void HeapPush(HP* php, HPDataType x)
{
	assert(php);
	// Space is not enough , Expand first 
	if (php->capacity == php->size)
	{
		size_t newCapacity = php->capacity * 2 + 1;
		HPDataType* tmp = realloc(php->a, sizeof(HPDataType) * newCapacity);
		if (tmp == NULL)
		{
			printf("realloc failed.\n");
			exit(-1);
		}
		php->a = tmp;
		php->capacity = newCapacity;
	}
	// Insert data into the heap —— Adjust the algorithm up 
	// First step ： First put the new data in the physical structure （ The order sheet / Array ） Tail of 
	php->a[php->size] = x;
	++php->size;
	// The second step ： Adjust up 
	AdjustUp(php->a, php->size - 1);
}
void HeapPrint(HP* php)
{
	assert(php);
	for (size_t i = 0; i < php->size; i++)
	{
		printf("%d ",php->a[i]);
	}
	printf("\n");
}

// Downward adjustment for a lot 
void AdjustDown(HPDataType* a,size_t size,size_t root)
{
	size_t parent = root;
	size_t child = parent * 2 + 1;
	while (child < size)
	{
		// First step ： Choose the older of the left and right children 
		if (child + 1 < size && a[child + 1] > a[child])
		{
			child++;
		}
		// If the child is bigger than the father, exchange , And continue to adjust down 
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
// Delete heap top data （ Little heap - Delete the minimum data at the top of the heap / A lot - Delete the maximum data at the top of the heap ）
// Keep small piles / The nature of the pile 
// If you directly move the remaining data forward , There's a problem ：① Destroy the structure ② The time complexity is O（N）, inconvenient 
// Better solution ： The first data is exchanged with the last data -> Don't erase the data , direct size-- that will do -> Downward adjustments 
void HeapPop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	// First step ： The root exchanges with the last data 
	Swap(&php->a[0], &php->a[php->size-1]);
	// The second step ： Delete data 
	--php->size;
	// The third step ： Downward adjustments 
	// Time complexity ：O(logN)
	AdjustDown(php->a,php->size,0);
}
HPDataType HeapTop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	return php->a[0];
}
size_t HeapSize(HP* php)
{
	assert(php);
	return php->size;
}
bool HeapEmpty(HP* php)
{
	assert(php);
	return php->size == 0;
}

main.c

#include"Heap.h"

void TestHeap()
{
	HP hp;
	HeapInit(&hp);
	HeapPush(&hp, 1);
	HeapPush(&hp, 5);
	HeapPush(&hp, 0);
	HeapPush(&hp, 8);
	HeapPush(&hp, 3);
	HeapPush(&hp, 9);
	HeapPrint(&hp);
	HeapPop(&hp);
	HeapPrint(&hp);
	HeapDesTroy(&hp);
}

// The steps of heap sorting are relatively simple , namely ：
// Put all the unordered elements in the array into a new heap , In turn pop Out , That is, the ordered element column 
// Heap sort —— Ascending 
//void HeapSort(HPDataType* a, int size)
//{
//	// First step ： Build a heap （ Little heap ）
//	HP hp;
//	HeapInit(&hp);
//	// The second step ： Put the unordered data in the array into the heap 
//	// The third step ： Because the small heap can pop up data from small to large in turn , So you can put it into the array in turn 
//	for (int i = 0; i < size; ++i)
//	{
//		HeapPush(&hp, a[i]);
//	}
//	size_t j = 0;
//	while (!HeapEmpty(&hp))
//	{
//		a[j] = HeapTop(&hp);
//		j++;
//		HeapPop(&hp);
//	}
//	HeapDesTroy(&hp);
//}
// Method 2 ： The space complexity is O(1)
// Ascending 
void HeapSort(HPDataType* a, size_t n)
{
	// Ascending sort , It is inconvenient to operate after building a small pile , It's better to bubble directly 
	// There are two ways to build a reactor 
	// One is to build a heap with the idea of adjusting the inserted data upward 
	// First step ： Build a heap on the basis of the original array 
	int i = 0;
	/*for (i = 1; i < n; i++)
	{
		AdjustUp(a, i);
	}*/
	// Be careful ： Direct downward adjustment cannot build a heap , Downward adjustment requirements ： The left and right trees are small piles / It's all piles 
	// Build the heap with downward adjustment , It should be the last one internal vertex Start , Adjust upside down 
	// The penultimate space internal vertice, That's the last leaf Parent node 
	for (i = (n - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n,i);
	}
	//① Heap sort （ Ascending ） Using the idea of reducing scale ：
	// Choose the maximum number for the first time , Then scale down to n-1......
	//② The essence of heap sorting is selective sorting 
	// Using the structure of the heap i The second election i Large number 
	size_t end = n - 1;
	while (end>0  )
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		end--;
	}
}

int main()
{/*
	TestHeap();*/
	HPDataType a[] = { 4,2,7,8,5,1,0,6 };
	HeapSort(a, sizeof(a) / sizeof(HPDataType));
	for (size_t i = 0; i <= 7; i++)
		printf("%d ", a[i]);
	return 0;
}

Two 、Top K problem

Problem description ： Find the first... In the data K The largest or smallest element . In general , The amount of data is relatively large .

The basic idea ： Use heap to solve .

Operation purpose ： The space complexity is O（1）, The time complexity is O（N）, Try to reduce the extra space .

First step ： Use the first... In the data set K Build a heap of elements

Seek before K The biggest element , Build small piles

Seek before K The smallest element , Build a lot of

The second step ： With the rest of N-K Elements are compared with the top of the heap

Seek before K The biggest element ： After building a small pile , If a residual element is larger than the top of the heap , It means that the remaining element should replace the top of the heap .

Seek before K The smallest element , After building a pile , If a residual element is smaller than the top of the heap , It means that the remaining element should replace the top of the heap .

Every time you replace , Is to eliminate the most unreasonable elements in the heap . For example, before seeking. K The biggest element , Replace... Once , Is to replace the smallest element in the small heap , Use one that is more likely to become a former K Replace it with a big element , Make the elements in the heap closer to the final result .

Code implementation ：

void PrintTopK(int* a, int n, int k)
{
	// First step : Build small piles 
	int* kminHeap = (int*)malloc(sizeof(int) * k);
	assert(kminHeap);
	// Put the elements in first 
	for (int i = 0; i < k; i++)
	{
		kminHeap[i] = a[i];
	}
	// Start with the penultimate non leaf node , Make a downward adjustment , Make it a small pile 
	for (int j = (k - 1 - 1) / 2; j >= 0; j--)
	{
		AdjustDown(kminHeap, k, j);
	}
	// The second step ： Element substitution 
	for (int i = k; i < n; i++)
	{
		if (a[i] > kminHeap[0])
		{
			Swap(&a[i], &kminHeap[0]);
			AdjustDown(kminHeap, k, 0);
		}
	}
	for (int i = 0; i < k; i++)
	{
		printf("%d ", kminHeap[i]);
	}
}

void TestTopK()
{
	int i;
	int* a = (int*)malloc(sizeof(int) * 5000);
	for (i = 0; i < 5000; i++)
	{
		a[i] = rand() % 1000000;
	}
	a[1] = 1000000 + 1;
	a[1237] = 1000000 + 3;
	a[1023] = 1000000 + 2;
	a[4900] = 1000000 + 4;
	PrintTopK(a, 5000, 4);
}
int main()
{/*
	TestHeap();*/
	/*HPDataType a[] = { 4,2,7,8,5,1,0,6 };
	HeapSort(a, sizeof(a) / sizeof(HPDataType));
	for (size_t i = 0; i <= 7; i++)
		printf("%d ", a[i]);
	return 0;*/
	TestTopK();
}