文章目录
- 优先级队列
- 几点说明
- 小根堆
- 大根堆
- 建堆算法
- 向下调整算法 & 初始化堆
- 代码:
- 向上调整算法 & 插入
- 删除
- 代码:
- 时间复杂度
- 手稿:
优先级队列
在优先级队列中存储的元素具有优先级,可以返回优先级较高的元素。
逻辑结构采用的是堆(完全二叉树),存储结构是用了数组(将二叉树层序遍历存储)
几点说明
- 设父节点的下标为i,那么左孩子的下标为2i+1,右孩子的下标为2i+2
小根堆
大根堆
建堆算法
向下调整算法 & 初始化堆
从最后一个根节点(也就是倒数第二层)
开始向上进行建堆,对每一棵子树都进行大(小)根堆的调整。
- 从两个(一个)子树中找到比根节点大(小)的结点,然后进行交换
- 父节点向上走(令parent = child),子节点也往上走(child = 2*parent+1)
需要注意的是:
① 不是每个结点都是有左(右)子树的,需要进行判断,防止越界
② 调整一直要进行到数组的末尾(child < array.length)
代码:
public PriorityQueue(int[] array) {this.array = new int[11];System.arraycopy(array,0,this.array,0,array.length);usedSize = array.length;// 只要根节点没有到顶,那就一直向上进行调整//(宏观向上寻找根节点,微观从每个根节点向下进行调整)for (int root = (array.length-1-1)/2; root >= 0; root--) {shiftDown(root, usedSize);}}public void shiftDown(int parent, int usedSize) {// 左孩子int child = 2 * parent + 1;// 因为是向下调整,所以找到头上的根节点后,一直向下走,// 直到不能再走(child < usedSize)while (child < usedSize) {// 如果右孩子的值更大,那就应该将child变为右孩子的下标,同时保证这个结点有右孩子if ((child + 1 < usedSize) && (array[child + 1] > array[child])) {child = 2 * parent + 2;}// 与根节点进行比较,如果孩子大,那就交换if (array[child] > array[parent]) {swap(child, parent);// 孩子和父亲都向下移动进行调整parent = child;child = 2 * parent + 1;} else {// 只要有一个结点不用调整,那就不需要继续往下走了,因为下面的之前已经调整过了break;}}
向上调整算法 & 插入
在插入的操作中,向上调整只需要进行一次,因为除了刚刚插进来的最后一个元素与其他的结点不匹配,其他的结点都已经在各自的树中形成自己的大根堆,所以只需要从最后一个结点出发向上调整,直到这个叶子结点变为新的根节点
(最大的根节点或者是某一层的新根节点再不能向上走)。
public void offer(int val) {// 先判断是否已满if (isFull() == true) {// 已满,扩容array = Arrays.copyOf(array, 2*array.length);}// 插到数组的最后一个位置array[usedSize++] = val;// 使用向上调整进行重新分配int child = usedSize-1;shiftUp(child);}private void shiftUp(int child) {int parent = (child - 1) / 2;// 只要这个插入的孩子节点没到根部,// 那就一直进行调整,或者到了某一层不用调整了while (child >= 0) {if (array[child] > array[parent]) {swap(child, parent);child = parent;parent = (child - 1) / 2;} else {break;}}}
删除
删除的就是堆头元素,最大(小)元素。
具体做法:
将堆头元素与末尾元素交换位置,随后对根节点所在的树进行向下调整。
- 问:为什么只用从根节点开始进行向下调整?
- 因为在之前的初始化过程中,所有树都已经是大(小)根堆,只有刚才进行交换的过程中,改变了根节点的数据使得这棵树不为大(小)根堆,所以只需要调整这棵树。
代码:
public void poll() {// 删除最大的元素,先将堆头的元素与最后一个进行交换,然后再进行向下调整swap(0, usedSize-1);usedSize--;// 只用调整根节点所在的那一棵树,因为其他的树在之前已经调整过了shiftDown(0,usedSize);}
时间复杂度
向下调整算法时间复杂度:O(n)
算最坏的情况(每次调整都需要从根一直调整到倒数第二层):
所以 每一层所需的次数就是结点数 * (高度-1)
(结点数为2h-1,高度为log2(n+1) )
之后利用错位相减法求得O(n)
向上调整算法时间复杂度:O(n*log~2~n)
算最坏的情况(每次调整都需要从叶子一直调整到根):
所以 每一层所需的次数就是结点数 * 层数
(结点数为2h-1,高度为log2(n+1) ,高度也即层数)
之后利用错位相减法求得O(n)