4. 堆

4.1 树与二叉树

树是一种数据结构，比如目录结构

树是一种可以递归定义的数据结构

树是由n个节点组成的集合：如果n=0，那这是一棵空树；如果n>0,那存在一个节点作为树的根节点，其他节点可以分为m个集合，每个集合本身又是一棵树

二叉树：度不超过二的树

满二叉树：除了叶子节点，其它节点都有左子树和右子树

完全二叉树：叶节点只能出现在最下层和次下层，并且最下面一层的节点都集中在该层最左边的若干位置的二叉树

二叉树的存储方式：链式存储和顺序存储

二叉树顺序存储方式下的编号：左：i -> 2i +1; 右：i ->2i +2

堆：是一种特殊的二叉树：

大根堆：一棵完全二叉树，满足任一节点都比其孩子节点大

小根堆：一棵完全二叉树，满足任一节点都比其孩子节点小

堆的性质：向下调整性质。当根节点的左右子树都是堆时，可以通过一次向下的调整来将其变换成一个堆

出数：每次拿最左边二叉树的叶子节点作为根节点，然后做向下调整

构造堆：看最后一个非叶子节点，每次调整小的

堆排序的过程：

1.建立堆，2.得到堆顶元素，为最大元素，3去掉堆顶，将堆最后一个碳元素放到堆顶，此时可以通过一次调整重新使堆有序，4.堆顶元素为第二大元素，5.重复步骤3，直到堆变空

代码实现：堆排序的时间复杂度是O（nlogn）

//Test example

//func main() {
//	s := []int{8, 23, 57, 74, 18, 17, 80, 89, 55, 9}
//	//调用
//	HeapSort(s)
//}

//将任意数列构造成堆并且将数据顺序打印

func HeapSort(s []int) {
	n := len(s)

	//遍历每一个非叶子节点，对每一个叶子节点进行整理

	for i := (n - 2) / 2; i >= 0; i-- {
		sift(s, i, n-1)
	}

	//顺序输出数列

	for j := n - 1; j >= 0; j-- {
		s[0], s[j] = s[j], s[0] //将最后一个元素与堆顶的元素交换位置
		sift(s, 0, j-1)         //调整：此时堆中还有n-1个数要出，因此最后一个元素索引是j-1
	}
	fmt.Println(s)
}

//堆的向下整理(对每一个非叶子节点操作)

func sift(s []int, low int, high int) {

	i := low      //根节点索引
	j := 2*i + 1  //根节点左孩子索引
	tmp := s[low] //将根节点先取出
work:
	for j <= high {
		if j+1 <= high && s[j] < s[j+1] { // 如果左孩子比右孩子小
			j = j + 1 //索引指向右孩子
			if s[j] > tmp {
				s[i] = s[j] //如果右孩子比根节点大，将右孩子填充到根节点位置
				i = j       //以右孩子所在的位置遍历下一层
				j = 2*i + j
				s[i] = tmp
				continue work
			} else { //如果右孩子小于根节点，则将根节点原来的值填回去，并终止程序
				s[i] = tmp
				break
			}
		} else {
			if s[j] > tmp {
				s[i] = s[j]
				i = j //以右孩子所在的位置遍历下一层
				j = 2*i + j
				s[i] = tmp
				continue work
			} else {
				s[i] = tmp
				break
			}
		}
		s[i] = tmp
		break
	}
}