堆的定义
堆必须是一个完全二叉树
大根堆:父节点元素都大于子节点元素
小根堆:父节点元素都小于子节点元素
完全二叉树的下标规律:若父节点下表为i,则左子节点下标为2i+1,右子节点下表为2i+2
堆的基本操作
两个基本操作:上滤/下滤
下滤:根节点向下调整 ,时间复杂度O(logn)
上滤:子节点向上调整,主要用于插入新元素到堆中,时间复杂度O(logn)
乱序数组建堆
自顶向下/自下而上
自顶向下建堆法 : 1. 插入堆(放入堆的最后一位) 2. 上滤
时间复杂度:O(nlogn)
自下而上建堆法 : 1. 建堆 2.每个父节点下滤,直到根节点操作完毕
时间复杂度:O(n)
优先级队列
插入队列:上滤
时间复杂度:O(logn)
弹出最小元素:弹出小根堆的根节点,把最后一个元素放在根节点,然后进行下滤操作
时间复杂度:O(logn)
堆排序
将优先级队列的所有元素依次弹出
考虑到空间复杂度,排序的结果会存放到堆空缺的单元里:用大根堆
时间复杂度:O(nlogn)