Binary tree structure and heap structure foundation

1 Binary tree structure

Binary tree （binary tree） It means that the degree of nodes in the tree is not greater than 2 The ordered tree of , It's the simplest and most important tree . The recursion of binary tree is defined as ： A binary tree is an empty tree , Or a tree made up of a root node and two disjoint trees , They are called non empty trees composed of left and right subtrees of roots respectively ; The left subtree and the right subtree are also binary trees  .

1、 Full binary tree ： If a binary tree has only a degree of 0 The node and degree of are 2 The node of , And the degree is 0 The nodes of are on the same layer , Then this binary tree is a full binary tree [4]  .

2、 Perfect binary tree ： Depth is k, Yes n A binary tree of nodes if and only if each node has a depth of k From the full binary tree of 1 To n When the nodes of are one-to-one corresponding , It's called a complete binary tree  [4]  .

The characteristic of complete binary tree is that leaf nodes can only appear on the two largest layers of sequence , And the maximum sequence of the descendants of the left branch of a node is equal to or larger than that of the descendants of the right branch 1 [4]  .

For a complete binary tree, the following properties are satisfied , Example ：

2 Heap structure

1. Heap structure is a complete binary tree structure realized by array

2. In a complete binary tree, if the maximum value of each subtree is at the top, it is a large root heap

3. In a complete binary tree, if the minimum value of each subtree is at the top, it is the small root heap

4. Reactor structure heapInsert And heapify operation

① How to adjust an array to a large root heap

heapinsert principle —— Compare with the parent node every time

Add the numbers in the array to the heap in turn . For each number added to the heap , Compare it with the value of its parent node , If he's older , Then the values of the parent node and the parent node are exchanged . His index position is  i , Then the index position of the parent node is  (i-1)/2 .

notes ：-1/2 As the result of the 0, therefore index=0 Don't be afraid when you are
 

#include<iostream>
#include<vector>
using namespace std;
 
void heapinsert(vector<int>&nums){
	if(!nums.size()) return;
 
	int temp=0, index=0;
	for(int i=0; i<nums.size(); i++){
 
		index=i;
		// -1/2 As the result of the 0, therefore index=0 Don't be afraid when you are 
		// Constantly compare with the parent node 
		while(nums[index]>nums[(index-1)/2]){
			temp=nums[index];
			nums[index]=nums[(index-1)/2];
			nums[(index-1)/2]=temp;
			index=(index-1)/2;
		}
	}
	
	for(auto i:nums)
		cout<<i<<endl;
}
 
int main(){
	vector<int>nums={1,2,3,4,5,6,7,8,9};
	heapinsert(nums);
 
	return 0;
}

②heapify The process —— Compare with child nodes every time

A value in the heap has changed , How to adjust .

For example, in the large root heap , The index location is  i  The value of the element of has changed （ smaller ）, Compare it with the left and right children , Exchange them with older children .  The index position of the left child is  2*i+1 ,  The index position of the right child is  2*i+2.

#include<iostream>
#include<vector>
using namespace std;
 
void heapify(vector<int>&nums){
	if(!nums.size()) return;
 
	int largest=0, i=0, temp=0;
	for(int index=0; index<nums.size(); index++){
		i=index;
		while((2*i+1)<nums.size()){
			
			// First judge whether the right child has crossed the boundary , Choose the older of the two children , Store the index position of the larger one in largest in 
			largest=(2*i+2)<nums.size()?
				nums[2*i+1]>nums[2*i+2]?2*i+1:2*i+2
			:2*i+1;		
		
			// explain nums[i] Can't move down any more 
			if(nums[i]>=nums[largest]) break;
 
			// Exchange the values of two elements 
			temp=nums[i];
			nums[i]=nums[largest];
			nums[largest]=temp;
 
			// Now it's time to continue the downward comparison 
			i=largest;
		}
	}
	
	for(auto i:nums)
		cout<<i<<endl;
}
 
int main(){
	vector<int>nums={1,9,8,7,6,5,4,3,2};
	heapify(nums);
 
	return 0;
}

5. Increase and decrease of heap structure

6. Priority queue structure , Introduce the heap structure

3 Heap sort

1. Let's make the whole array into a big root heap structure , The process of building a heap ：

① From top to bottom , The time complexity is 0(N*logN)

② The bottom-up approach , The time complexity is 0(N)

2. Swap the maximum value of the heap with the value at the end of the heap , And then reduce the size of the heap , Then adjust the stack , It's been going on and on , The time complexity is O(N*logN)

3. The size of the heap is reduced to 0 after , Sort complete

4 Heap sort extension problem

We know an almost ordered array , Almost orderly means , If you put the array in order , Each element can move no more than k, also k Smaller than array . Please select an appropriate sorting algorithm to sort the data .

Their thinking ：

Prerequisite ： Given an array arr, as well as k=6

① First, traverse the first seven numbers of the array , Put it in the small root pile

② The minimum value must be in the first position after sorting , Set the minimum value of the small root heap eject （ Remove from the small root heap and place in 0 Location ）

③ Then put the next data into the small root heap , The next steps are the same as ②

④ Go round and round until the end of the array , Pop up the data of the small root heap in turn