“This is the 21st day of my participation in the Gwen Challenge in November. See details: The Last Gwen Challenge in 2021”

Heap sort

ascending

A very normal idea space complexity O(N)

Push all the elements of the array into the small heap, and then take the top element of the heap back into the array to achieve the effect of ascending

HeapSort heap ascending function

/ / ascending
void HeapSort(HPDataType* a,int n)
{
	HP hp;
	HeapInit(&hp);
	int i = 0;
	// Create a small heap
	for (i = 0; i < n; i++)
	{
		HeapPush(&hp, a[i]);
	}
	// Then put the top element back into the array
	for (i = 0; i < n; i++)
	{
		a[i] = HeapTop(&hp);
		// Pop it off
		HeapPop(&hp);
	}
	HeapDestroy(&hp);
}
Copy the code

Heap sort test function

void testHeapSort(a)
{
	int a[] = { 40.2.0.12.5.454.2323 };
	/ / heap sort
	HeapSort(a, sizeof(a) / sizeof(a[0]));
	int i = 0;
	for (i = 0; i < sizeof(a) / sizeof(a[0]); i++)
	{
		// Get the elements out of the array
		printf("%d ",a[i]);
	}
    printf("\n");
}
Copy the code

Build heap (build heap up and down)

Adjust up (build heap)

There is nothing wrong with the above method, but there is a requirement that the space complexity is O(1), which means that we can no longer use Heap

(Insert here is not really insert, because the data is already there, we are just tuning the heap, like insert.)

So if we look at the print above we see that we’re building a small heap, but the bad thing is we’re building the smallest one at index zero, and then we’re building the smallest one at index one, and that’s not going to work, because it’s going to break the structure, so we’re going to have to start from the top of the heap, and then we’re going to end up swapping

// Real gameplay
void HeapSort(HPDataType* a, int n)
{
	assert(a && n>=0);
	// Build the array a into a heap
	int i = 0;
	for (i = 0; i < n; i++) { AdjustUp(a,n,i); }}Copy the code

Swap sort && and adjust it up again

Heap sort code

// Real gameplay
void HeapSort(HPDataType* a, int n)
{
	assert(a && n>=0);
	// Build the array a into a heap
	int i = 0;
	// Adjust upward
	for (i = 0; i < n; i++)
	{
		AdjustUp(a,i);
	}
	// The root swaps with the last number and finds the next largest number each time
	int tail = n - 1;
	while (tail)
	{
		Swap(&a[0], &a[tail]);// The root is swapped with the last number
		tail--;
		for (i = 0; i <= tail; i++) { AdjustUp(a, i); }}}Copy the code

Heap sort test

void testHeapSort(a)
{
	int a[] = { 40.2.50.12.5.454.2323};/ / heap sort
	HeapSort(a, sizeof(a) / sizeof(a[0]));
	int i = 0;
	for (i = 0; i < sizeof(a) / sizeof(a[0]); i++)
	{
		// Get the elements out of the array
		printf("%d ",a[i]);
	}
	printf("\n");
}
Copy the code

Downward adjustments

Build small heaps in ascending order

Build a heap in ascending order

That’s how you play it

Heap sort

// Real gameplay
void HeapSort(HPDataType* a, int n)
{
	assert(a && n>=0);
	// Build the array a into a heap
	int i = 0;
	//// Adjust upward
	//for (i = 0; i < n; i++)
	/ / {
	//	AdjustUp(a,n,i);
	/ /}
	// Adjust downward
	for (i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}
	// The root swaps with the last number and finds the next largest number each time
	int tail = n - 1;
	for (i = tail; i > 0; i--)
	{
		Swap(&a[0],&a[i]);// The root is swapped with the last number
		AdjustDown(a, i, 0);// Adjust down to find the next largest number every time}}Copy the code

Test heap sort

void testHeapSort(a)
{
	int a[] = { 40.2.50.12.5.454.232.30.3.10 };
	/ / heap sort
	HeapSort(a, sizeof(a) / sizeof(a[0]));
	int i = 0;
	for (i = 0; i < sizeof(a) / sizeof(a[0]); i++)
	{
		// Get the elements out of the array
		printf("%d ",a[i]);
	}
	printf("\n");
}
Copy the code

Descending order

Adjust upward (build small piles)

Adjust downward (build small heap)

Time complexity to build the heap

3.2.3 Time complexity of heap construction since the heap is a complete binary tree, and the full binary tree is also a complete binary tree, the full binary tree is used here to prove it for simplicity (the time complexity is an approximation originally, and more nodes will not affect the final result) :

So the time is order n.