Pile up study notes and 1098 insertion or head sort (25 points)

1. Definition of heap:

The heap is a complete binary tree. It can be divided into large top heap (the value of the parent node is greater than or equal to the value of the child node) and small top heap (the value of the parent node is less than or equal to the value of its child node).

2. Storage of heap:

Array is used to store the complete binary tree. If the first node is in position 1 of the array, the left child of the i node is in position 2i, and the right child is in position (2i+1).

const int maxn=100;
int heap[maxn];

3. build heap:

First of all, it is clear that if the number of elements in the sequence is n, then the number of leaf nodes in the complete binary tree is n / 2 (round up).
For a given sequence, the process of heap building starts from the nth / 2nd (round down) node to the first node, and adjusts each traversal node downward.

//Downward adjustment (take the large top reactor as an example)
void downAdjust(int low,int high){
int i=low,j=2*j;
while(j<=high){ //Left child node exists
 //There is a right child node and the value of the right child node is greater than that of the left child node (that is, let j store the coordinates of the child node with the larger value)
 if(j+1<=high && heap[j+1]>heap[j]){
  j=j+1;
  }
 
 if(heap[j]>heap[i])
 {
  swap(heap[j],heap[i]);
  i=j;   //After downward adjustment once, it is also necessary to judge whether it is necessary to continue downward adjustment, so that i remains the node to be adjusted
  j=2*i;
  }else{  //The current node and its left and right child nodes meet the definition of big top heap, and the adjustment ends
  break;}
}}

//Build heap
void createHeap(){
 for(int i=n/2;i>=1;i--)
   downAdjust(i,n);
   }

4. Insert elements into the heap:

(take the large top reactor as an example)
Put the element to be added in the last n+1 position of the array, and then adjust it upward (compare the element to be adjusted with its parent node, if the weight is larger than the parent node, exchange it with the parent node, and repeatedly compare until the weight of the parent node is larger).

5. Heap sorting:

(assume that the current heap is a large top heap, and you want to autoincrement sort)
Take out the top element of the heap, replace the last element of the heap to the top of the heap (that is, move the large element to the end of the array), and make a downward adjustment for the top element of the heap (make sure that the top of the heap is the maximum value). Repeat the above steps until there is only one element in the heap.

void heapSort()
{
 createHeap();
 for(int i=n;i>=1;i--)
 {
  swap(heap[i],heap[1]);
  downAdjust(1,i-1);  //Every time the top of the heap is adjusted, the number of elements in the heap is reduced by one
  }
  }
 

6. practice

1098 insertion or head sort (25 points)

(refer to the ideas in algorithm notes and add some of my own understanding)
For some parts with independent logic or functions, they can be taken out as a function separately, so as to avoid confusion in thinking when writing all of them in the main function (for example, in this question, I will decide whether to insert sorting and whether to use heap sorting as a function separately).

const int maxn=120;
int given[maxn], temp[maxn], flagArr[maxn];//Original array, original array backup, target array
int n;

bool cmpSame(int arr1[], int arr2[])//Used to compare whether two arrays are the same
{
	for (int i = 1; i <= n; i++)
		if (arr1[i] != arr2[i])
			return false;
	return true;
}
bool insertSort()
{
	for (int i = 2; i <= n; i++)  //Insert sort from second element
	{
		//After each insertion sorting, the current intermediate sequence should be compared with the target sequence. Note that i!=2 is because the initial sequence is not an intermediate sequence
		if (i != 2 && cmpSame(temp, flagArr)) {
			//Sort again
			sort(temp + 1, temp + i + 1);
			return true;
		}
		//The insertion sort process can be performed directly with the sort function
		sort(temp + 1, temp + i + 1);
	}
	return false;
}

void downAdjust(int low, int high)
{
	//i is the node to be adjusted, j is its left child node
	int i = low, j = 2 * i;
	while (j <= high)
	{
		if (j + 1 <= high && temp[j + 1] > temp[j])
			j = j + 1;  //j is the subscript of the higher valued child node
		if (temp[i] < temp[j])  //The value of the parent node is less than the value of the child node
		{
			swap(temp[i], temp[j]);
			i = j;  //Make i always the subscript of the node to be adjusted
			j = 2 * i;
		}
		else {
			break;
		}
	}
}
//Heap sort
void heapSort()
{
	//Build a heap before sorting the heap
	for (int i = n / 2; i >= 1; i--)
		downAdjust(i, n);
	for (int i = n; i > 1; i--)
	{
		if (i != n && cmpSame(temp, flagArr))
		{
			swap(temp[1], temp[i]);
			downAdjust(1, i - 1);
			return;
		}
		swap(temp[1], temp[i]);
		downAdjust(1, i - 1);
	}
}
int main()
{
	scanf("%d", &n);
	//Since heap sorting is used, array subscripts start at 1
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &given[i]);
		temp[i] = given[i];
	}
	for (int i = 1; i <= n; i++)
		scanf("%d", &flagArr[i]);
	if (insertSort())
	{
		printf("Insertion Sort\n");
		for (int i = 1; i < n; i++)
			printf("%d ", temp[i]);
		printf("%d", temp[n]);
	}
	else {
		printf("Heap Sort\n");
		for (int i = 1; i <= n; i++)
			temp[i] = given[i];
		heapSort();
		for (int i = 1; i < n; i++)
			printf("%d ", temp[i]);
		printf("%d", temp[n]);
	}
}
Published 7 original articles, won praise 1, visited 160
Private letter follow

Tags: less

Posted on Fri, 14 Feb 2020 08:22:34 -0800 by shrike202