树是一种数据结构，比如目录结构
树是一种可以递归定义的数据结构
树是由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{2, 8, 5, 6, 3, 9, 7, 1, 25, 23, 14, 0}
// HeadSort(s)
//}
func HeadSort(s []int) {
n := len(s)
//将任意数列构造成堆
for i := (n - 2) / 2; i >= 0; i-- {
sift(s, i, n-1)
}
fmt.Println("排好的堆是：", s)
//将堆从小到大排序
for j := n - 1; j >= 0; j-- {
s[0], s[j] = s[j], s[0]
sift(s, 0, j-1)
}
fmt.Println("堆中元素按照顺序输出：", s)
}
//定义节点整理函数，将给定节点整理成堆
func sift(s []int, low int, high int) {
//定义两个指针
i := low //第一个指针指向根节点
j := 2*i + 1 //第二个指针指向根节点的左孩子
tmp := s[low] //将根节点的数先取出存放
for j <= high { //保证叶子节点不越界
if j+1 <= high && s[j] < s[j+1] { //在右孩子有且大于左孩子的情况下，j越界会退出for循环，左孩子大时会执行下一个if语句
j = j + 1 //第二个指针指向右孩子
}
if s[j] > tmp { //右孩子大于根节点
s[i] = s[j] //将右孩子填充至根节点
i = j //将右孩子作为根节点，遍历下一层1
j = 2*i + 1
s[i] = tmp //将根节点填充到右孩子的位置，重新开始遍历
} else { //右孩子小于根节点，不做改变
s[i] = tmp
break
}
}
//fmt.Println(s) 测试代码
}
4.2 堆排序的应用 TOPK问题
现在有n个数，设计算法得到前k个大的数（k 解决思路： 排序后切片（O(nlogn)）; owB三人组（冒泡排序、选择排序、插入排序 O(n*n）） 冒泡排序：需要k躺，O(kn) 插入排序：维护一个长度为k的列表，如果新来的数大于列表最后一个值，则插入 选择排序：选择100次 堆排序 O(nlogk) 取列表的前k个元素建立一个小根堆，堆顶就是目前第k大的数 依次向后遍历列表，对于列表中的元素，如果小于堆顶，则忽略该元素，如果大于堆顶，则将堆顶更换为该元素，并且对堆进行一次调整 遍历列表所有元素后倒叙弹出堆顶 我们来看看代码//Topk 问题算法
//Test example
//func main() {
// //将下列随机数列顺序最大的七位
// s := []int{2, 8, 5, 6, 3, 9, 7, 1, 25, 23, 14, 0}
// Topk(s, 7)
//}
func Topk(s []int, k int) {
heap := s[0:k]
//建堆
for i := (k - 2) / 2; i >= 0; i-- {
sift(heap, i, k-1)
}
fmt.Println("新建的小根堆是：", heap)
//遍历列表中所有剩余元素，如果大于堆顶，则纳入重新调整
for j := k; j < len(s); j++ {
if s[j] > heap[0] {
heap[0] = s[j]
Sift(heap, 0, k-1)
}
}
fmt.Println("遍历后重新调整过的堆是：", heap)
//挨个输出
for h := k - 1; h >= 0; h-- {
s[0], s[h] = s[h], s[0]
Sift(s, 0, h-1)
}
fmt.Println("堆中元素按照顺序输出：", heap)
}
//定义节点整理函数，将给定节点整理成小根堆
func Sift(s []int, low int, high int) {
//定义两个指针
i := low //第一个指针指向根节点
j := 2*i + 1 //第二个指针指向根节点的左孩子
tmp := s[low] //将根节点的数先取出存放
for j <= high { //保证叶子节点不越界
if j+1 <= high && s[j] > s[j+1] { //在右孩子有且大于左孩子的情况下，j越界会退出for循环，左孩子小时会执行下一个if语句
j = j + 1 //第二个指针指向右孩子
}
if s[j] < tmp { //右孩子小于根节点
s[i] = s[j] //将右孩子填充至根节点
i = j //将右孩子作为根节点，遍历下一层1
j = 2*i + 1
s[i] = tmp //将根节点填充到右孩子的位置，重新开始遍历
} else { //右孩子大于根节点，不做改变
s[i] = tmp
break
}
}
//fmt.Println(s) 测试代码
}
