(heap sort) heap sort is super detailed, I don't believe you can't (C language code implementation)

The basic introduction of heap

Pile up (Heap) Is a general term for a special class of data structures in computer science .
A heap is usually a tree that can be seen as a tree Perfect binary tree Array object of . Store all its elements in a one-dimensional array in the order of a complete binary tree , And satisfy that the value of any parent node must be less than or equal to ( Greater than or equal to ) The value of the child node .

Two properties of heap ：

• The value of a node in the heap is always no greater than or less than the value of its parent node
• The heap is always a complete binary tree .

The classification of heaps ：

• Heap ( Little heap )： The smallest heap in the root node
• Big root pile ( A lot )： The largest heap at the root node

---

The implementation of heap sorting

Since it's heap sorting , We have to build a heap , Sort on the basis of the heap .

First, build a heap , Then how can we make a pile of disordered numbers form a pile ？

First of all, we need to understand the basic algorithm of heap sorting —— Adjust the algorithm down

---

Building the heap ( Adjust the algorithm down )

First we give an array , Logically, it's a complete binary tree .
int array[] = {27,15,19,18,28,34,65,49,25,37};

This is a group Special data , But this group of data just meets the condition of downward adjustment algorithm

The downward adjustment algorithm has a premise ： The left and right subtrees must be a heap , To adjust .

We can go through Downward adjustment algorithm starting from the root node It can be adjusted into a small pile .

We can find that only the data of the root node does not satisfy the small heap , And the left and right subtrees are satisfied , So we need to adjust from the root node step by step , Make it form a small pile .

The basis of adjustment is the condition of small piles ： Any parent node is less than or equal to the child node .

Adjust the algorithm down ：

1. Start at the root node , Keep adjusting downward
2. Choose the smaller of the left and right children , Compared with my father

• If you are younger than your father , Just exchange with my father
• If you are older than your father , Just stop switching , At this time, the heap has been formed

3. At worst, the exchange stops when the child is a leaf node

Code implementation ：

// In exchange for 
void swap(int* px, int *py)
{
    
	int tmp = 0;
	tmp = *px;
	*px = *py;
	*py = tmp;
}

// Adjust the algorithm down , Conditions ： The left and right subtrees are piles 

// Let's assume a small pile ( A lot of them will be modified accordingly )

//a For array first address ,n Is the number of data ,parent Parent node 
void AdjustDown(int* a, int n, int parent)
{
    
	int child = parent * 2 + 1;// First, point to the left child by default 
	
    // The end condition is child The subscript of is less than n, When child When it is a leaf node , next step child Is greater than n Of , The loop ends 
	while (child < n)
	{
    
		// Find the small one around the child , send child For the younger child 
		if ((child + 1 < n) && (a[child + 1] < a[child]))
		{
    
			child++;// By default, the subscript of the right child is more than that of the left child 
		}

		//1. If a young child is younger than his father , The exchange , Continue to adjust downward 
		//2. If a young child is older than his father , End adjustment 

		if (a[child] < a[parent])
		{
    
			// In exchange for 
			swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
    
			break;
		}
	}
}

---

The downward adjustment algorithm is over , But we will find that this is very chicken ribs , A heap can only be formed under certain circumstances , So how to ensure that heaps can be formed in general ？

First, give a complete binary tree that is not satisfied that the left and right subtrees are stacked ,int arr[] = {12, 34, 45, 56, 14, 20, 90, 67, 42, 74};
We make this complete binary tree into a small pile .

Main idea ：

1. Adjust downward from the penultimate non leaf node
2. Stop when adjusting to the root node

Code implementation ：

// Build a small pile 
//i The initial value of is the subscript of the first non leaf node 
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
    
	// Adjust downward from the penultimate non leaf node , All the way to the root 
	AdjustDown(a, n, i);
}
// After adjustment, you get a small root pile 

After adjusting the operation of the algorithm downward , The generally complete binary tree has formed a heap , Now how to sort ？

---

The implementation of sorting

The implementation of sorting , We should consider the ascending order , Or in descending order , Building piles can be divided into building large piles and building small piles , So how to choose the best ？

Rank ascending ： It's better to build a lot , Small piles can also be built , Unable to reflect the value brought by reactor building
In descending order ： It's better to build small piles , Empathy

So how to sort ？

1. The pile has been built , The first value is the minimum ( If it's a lot , Then the first value is the largest ), Swap the first value with the last value , Store it
2. Remove the last number , Adjust downward from the root node , Repeat , Get the minimum value in turn and store , Until only the last number is left .

Code implementation ：

int end = n - 1;
	while (end > 0)
	{
    
		swap(&a[0], &a[end]);// Exchange the minimum value with the subsequent elements of the array , Store it behind the array , Form descending order 
		AdjustDown(a, end, 0);// Then adjust it in turn to get the minimum value 
		end--;
	}

---

Heap sort complete code

Moving graph ：

Code ：

#include<stdio.h>

// In exchange for 
void swap(int* px, int *py)
{
    
	int tmp = 0;
	tmp = *px;
	*px = *py;
	*py = tmp;
}

// Adjust the algorithm down , Conditions ： The left and right subtrees are piles 

// Let's assume a small pile ( A lot of them will be modified accordingly )
void AdjustDown(int* a, int n, int parent)
{
    
	int child = parent * 2 + 1;// By default, it points to the left child 

	while (child < n)
	{
    
		// Find the small one around the child 
		if ((child + 1 < n) && (a[child + 1] < a[child]))
		{
    
			child++;// By default, the subscript of the right child is more than that of the left child 
		}

		//1. If a young child is younger than his father , The exchange , Continue to adjust downward 
		//2. If a young child is older than his father , End adjustment 

		if (a[child] < a[parent])
		{
    
			// In exchange for 
			swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
    
			break;
		}
	}
}

void HeapSort(int* a, int n)
{
    
	// Build a small pile 
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
    
		// Adjust downward from the penultimate non leaf node , All the way to the root 
		AdjustDown(a, n, i);
	}
	// After adjustment, you get a small root pile 

	// In descending order 
	int end = n - 1;
	while (end > 0)
	{
    
		swap(&a[0], &a[end]);// Exchange the minimum value with the subsequent elements of the array , Store it behind the array , Form descending order 

		AdjustDown(a, end, 0);// Then adjust it in turn to get the minimum value 

		end--;
	}
}

int main()
{
    
	int a[] = {
     12, 34, 45, 56, 14, 20, 90, 67, 42, 74 };

	// Heap sort  
	HeapSort(a, sizeof(a) / sizeof(int));

	// Print data 
	for (int i = 0; i < sizeof(a) / sizeof(int); i++)
	{
    
		printf("%d ", a[i]);
	}
	return 0;
}

success ！！！

---

Time complexity analysis of reactor building

So the time complexity of heap sorting is O(N*log2N)(2 Base number )