二叉树结构以及堆结构基础

1 二叉树结构

二叉树（binary tree）是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。二叉树的递归定义为：二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树 。

1、满二叉树：如果一棵二叉树只有度为0的节点和度为2的节点，并且度为0的节点在同一层上，则这棵二叉树为满二叉树[4]  。

2、完全二叉树：深度为k，有n个节点的二叉树当且仅当其每一个节点都与深度为k的满二叉树中编号从1到n的节点一一对应时，称为完全二叉树 [4]  。

完全二叉树的特点是叶子节点只可能出现在层序最大的两层上，并且某个节点的左分支下子孙的最大层序与右分支下子孙的最大层序相等或大1 [4]  。

对于完全二叉树来说满足以下性质，例子：

2 堆结构

1. 堆结构就是用数组实现的完全二叉树结构

2. 完全二叉树中如果每棵子树的最大值都在顶部就是大根堆

3. 完全二叉树中如果每棵子树的最小值都在顶部就是小根堆

4. 堆结构的heapInsert与heapify操作

①如何把数组调整成一颗大根堆

heapinsert原理——每次都与父节点进行比较

将数组中的数字依次加入到堆中。对于每一个加入到堆中的数字，将其与其父节点的值进行比较，如果他大，则将他和他父节点的值进行交换。他的索引位置为  i ，则其父节点的索引位置为  (i-1)/2 。

注：-1/2的结果为0，所以index=0的时候也不用怕
 

#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的结果为0，所以index=0的时候也不用怕
		//不断的与父节点进行比较
		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过程——每次都与子节点进行比较

堆中某个值发生了变化，如何调整。

比如大根堆中，索引位置为 i 的元素的值发生了改变（变小），则将其与左右两个孩子进行比较，将其与较大的孩子进行交换。 左孩子的索引位置为 2*i+1 , 右孩子的索引位置为 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()){
			
			//先判断右孩子是否越界，再选择两个孩子中的较大者，将大者的索引位置存入largest中
			largest=(2*i+2)<nums.size()?
				nums[2*i+1]>nums[2*i+2]?2*i+1:2*i+2
			:2*i+1;		
		
			//说明nums[i]已经不能再向下移动了
			if(nums[i]>=nums[largest]) break;
 
			//交换两个元素的值
			temp=nums[i];
			nums[i]=nums[largest];
			nums[largest]=temp;
 
			//此时该继续向下比较了
			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. 堆结构的增大和减少

6. 优先级队列结构，介绍堆结构

3 堆排序

1. 先让整个数组都变成大根堆结构，建立堆的过程：

①从上到下的方法，时间复杂度为0(N*logN)

②从下到上的方法，时间复杂度为0(N)

2. 把堆的最大值和堆末尾的值交换，然后减少堆的大小之后，再去调整堆，一直周而复始，时间复杂度为O(N*logN)

3.堆的大小减小成0后，排序完成

4 堆排序扩展题目

已知一个几乎有序的数组，几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离可以不超过k，并且k相对于数组来说较小。请选择一个合适的排序算法针对这个数据进行排序。

解题思路：

前提条件：给定一个数组arr，以及k=6

①首先遍历数组前七个数，将其放入小根堆

②排完序后最小值肯定在第一个位置，将小根堆的最小值弹出（从小根堆移除放在0位置）

③接着将下一个数据放入小根堆，接下来步骤同②

④周而复始直到数组的最后，将小根堆的数据依次弹出即可