【从堆的定义到优先队列、堆排序】 10分钟看懂必考的数据结构——堆

# 堆： 了解下就好
# 一、堆是完全二叉树的结构
# 什么是完全二叉树：1.只允许最后一行不满 2.最后一行必须从左往右排，中间不能有间隔
# 二、堆序性 1.小根堆，父节点都要更小 2.大根堆，父节点都要更大
# 三、堆的存储，因为是完全二叉树，所以可以根据层序遍历，来得到一个数组，此时，父节点为i时，左右子节点一定为2i+1/2
# 四、堆有两个基本操作：1.上滤，通常用于插入新元素到根中时，向上调整位置时
# 2.下滤（因为必须要满足堆序性的话，所以对不满足的要操作），把根节点向下调整的操作叫下滤
# 五、自顶向下建堆法：1.插入堆 2.上滤
# 六、自下而上建堆法：对每个父节点进行下滤（从最下面的父节点开始）-- 复杂度O(N)
# 七、应用 1.优先队列：弹出最小元素 -- 可以用来实现堆排序，用大根堆排序完，弹出的是正序，小根堆反 2.插入：就是上滤