Sort 4-heap sort and massive TOPK problem

One 、 Heap sort

（1） The heap is a complete binary tree
（2） The value of each node of the heap is greater than or equal to its left and right child nodes, which is called a heap
（3） The value of each node of the heap is less than or equal to its left and right child nodes, which is called small heap
Pile up ： Those with the above conditions are called heaps

We can see that the top of the pile is the maximum , The top of a small heap is the minimum .
Note from the heap ： The following node must be the largest （ Small ） person .

The structure of the pile ：
Take the above pile as an example ： If you store a large number of sequence traversals into an array , Then the following relationship is satisfied

Left child coordinates =2 Father coordinates +1
Right child mark =2 Father coordinates +2

Let's talk about this heap structure , Its purpose is for heap sorting .

. Heap sort algorithm

Heap sort ： The sequence to be sorted is constructed into a large （ Small ） Pile up , The alignment of the whole sequence （ Small ） Value is the root node at the top of the heap . Take it away , And then put the rest of n-1 A sequence is reconstructed into a heap , You can get the second largest （ Small ） Value , So again and again , Then we can get an ordered sequence .

Downward adjustment of heap ：
Premise ： The left and right subtrees must be heaps
By adjusting down , Pile up the whole tree

1. Choose the one between the left and right children .
2. Young children are compared with their father .
3. If a young child is younger than his father , Exchange with my father , And continue to adjust the original position of the original child down .
4. If a young child is older than his father , There is no need to deal with , Adjustment complete .

void Swap(int *p,int *q)
{
	int temp = *p;
	*p = *q;
	*q = temp;
}


void AdJustDown(int *arr,int n,int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child+1<n && arr[child + 1] < arr[child])
		{
			child++;
		}
		if (arr[parent] > arr[child])
		{
			Swap(&arr[parent],&arr[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}

	}
	
}

int main()
{
	int arr[] = { 27, 15, 19, 18, 28, 34, 65, 44 };
	int sz=sizeof(arr)/sizeof(arr[0]);	
	AdJustDown(arr,sz,0);
	for (int i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}

}

Build a pile ：
In ascending order to build a lot of , Build small piles in descending order .

1. Build a pile
2. Bottom up , From right to left

Build a pile yes Bottom up , From right to left

#include<stdio.h>

void Swap(int *p,int *q)
{
	int temp = *p;
	*p = *q;
	*q = temp;
}

void AdJustDown(int *arr,int n,int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child+1<n && arr[child + 1] < arr[child])
		{
			child++;
		}
		if (arr[parent] > arr[child])
		{
			Swap(&arr[parent],&arr[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}

	}
	
}
void HeaqSort(int *arr,int n)
{
	// Build a pile , Bottom up , From right to left .
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdJustDown(arr, n, i);
	}
	// Heap sort 
	//int end = n - 1;
	//while (end>0)
	//{
		//Swap(&arr[0],&arr[end]);
		//AdJustDown(arr,end, 0);
		//end--;
	//}
}

int main()
{
	int arr[] = { 27, 15, 11, 18, 28, 4, 65, 44 };
	int sz=sizeof(arr)/sizeof(arr[0]);	
	HeaqSort(arr, sz);
	for (int i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}

}

Heap sort ：

void HeaqSort(int *arr,int n)
{
	// Building the heap 
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdJustDown(arr, n, i);
	}
	// Heap sort 
	int end = n - 1;
	while (end>0)
	{
		Swap(&arr[0],&arr[end]);
		AdJustDown(arr,end, 0);
		end--;
	}
	
}

The downward adjustment method is complex ：log₂ⁿ
Reactor building time complexity ：O(N)
The time of heap sorting is complex ：O(N*log₂^N)
Build the pile as follows ：
We use full binary tree to calculate , The height of the stack is h, Suppose the height of each floor is hi, The number of nodes in each layer is ni, The time of building the reactor is complex ：

so ： The complexity of time is O(N)

Two 、 Massive TopK problem

Train of thought ： Direct heap sort
Time complexity ：O(Nlog₂^N)
Train of thought two ： Time complexity :O(Nlog₂^k), Spatial complexity O(K)

1. First put the array K Data , Build a pile
2. And then the rest N-K Number , Compare with the data on the top of the pile , If it is smaller than the data at the top of the heap , Replace the data at the top of the heap , Then adjust the heap ( This heap adjustment is before the adjustment K One of the ).
3. Then in front of the pile K The number is K Small value

 void Swap(int *p,int *q)
{
	int temp = *p;
	*p = *q;
	*q = temp;
}


void AdJustDown(int *arr,int n,int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child+1<n && arr[child + 1] > arr[child])
		{
			child++;
		}
		if (arr[parent] < arr[child])
		{
			Swap(&arr[parent],&arr[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}

	}
	
}
void HeaqSort(int *arr,int n)
{
	// Building the heap 
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdJustDown(arr, n, i);
	}
}

int* getLeastNumbers(int* arr, int arrSize, int k, int* returnSize)
{
    int i=k;
    HeaqSort(arr,k);
    for(int k=0;k<arrSize;k++)
    {
       printf("%d ",arr[k]);
    }
    while(i<arrSize)
    {
        if(arr[i]<arr[0])
        {
            Swap(&arr[i],&arr[0]);
            AdJustDown(arr,k,0);
            i++;
        }
        else
        {
            i++;
        }
    }
    int*retarr=(int *)malloc(sizeof(int)*k);
    for(int j=0;j<k;j++)
    {
        retarr[j]=arr[j];
    }
    *returnSize=k;
    return retarr;

}

Thank you for making mistakes .