java学习笔记之优先队列实现原理

2024-07-15 12:13| 来源: 网络整理| 查看: 265

目录一、二叉堆的基本原理(一) 什么是二叉堆？(二) 堆的用途(三) 堆的基本操作1. 插入上浮 2. 删除下沉二、PriorityQueue(一) PriorityQueue是什么？(二) PriorityQueue的使用(三) PriorityQueue的实现原理插入删除三、PriorityBlockingQueue(一) PriorityBlockingQueue是什么？(二) PriorityBlockingQueue的实现原理插入删除四、DelayQueue五、DelayedWorkQueue六、一图胜千言添加删除七、F&Q

普通的队列是先进先出的数据结构，而优先队列为元素赋予优先级，具有最高优先级的元素成为队列首部。

优先队列一般基于二叉堆实现。

本文会分析java中几种常见的优先队列：PriorityQueue、PriorityBlockingQueue、DelayQueue、DelayedWorkQueue。

一、二叉堆的基本原理 (一) 什么是二叉堆？完全二叉树堆的根节点的优先级最大（即最大或最小）父节点的优先级必定大于子节点，兄弟节点的优先级不确定谁大谁小时间复杂度插入O(log n)删除O(log n)构造O(n) (二) 堆的用途取最值 (三) 堆的基本操作 1. 插入

往堆插入元素，基本思想是从最后一个位置开始，通过上浮操作不断调整位置，直到满足父节点的优先级必定大于子节点这个条件。

上浮

上浮是往二叉堆添加元素用到的操作，它其实是不断的调整k的位置为父元素的位置直到满足条件为止。

// 用数组表示堆 Object []objs = new Object[10]; /** * 上浮： * k表示堆的最后一个位置； * obj表示将要插入的元素。 */ private void siftUp(int k, Object obj) { // 1. 判断k是否为根元素的位置0，如果是则直接赋值 while(k>0) { // 2. 获取父元素的位置,parent = (k-1)/2 int parent = (k-1) >>> 1; // 3. 如果父元素的优先级大于等于obj，跳出循环并插入obj if(objs[parent] >= obj) { break; } // 4. 如果父元素的优先级小于obj，将父元素赋值到k的位置，更改k为父元素的位置，继续循环 objs[k] = objs[parent]; k = parent; } // 5. 为obj赋值 objs[k] = obj; } /** * 添加元素，不考虑数组扩容的情况。 * 假设size表示当前堆包含的元素个数（注意不一定等于上面定义的10） */ public void add(Object obj) { if(size==0) { objs[0] = obj; } else { siftUp(size, obj); size++; } } 2. 删除

删除指定位置的元素，其基本思想是从指定位置开始，把最后一个元素放到被删除元素的位置，通过下沉或者上浮操作，使得堆满足父元素优先级大于子元素的条件。

下沉

下沉是删除时用到的操作。它是把最后一个元素放到被删除元素的位置，然后重新调整使得堆满足条件的过程。

当被删除元素的位置位于最后一个元素的父元素的位置后面时，可以直接把最后一个元素插入到被删除元素的位置；然后再进行上浮操作。否则，需要执行下沉操作。 // 用数组表示堆 Object []objs = new Object[10]; /** * k被删除元素的位置； * obj堆的最后一个元素； * 假设size为当前堆包含元素的个数（不一定是上面定义的10） */ private void siftDown(int k, Object obj) { // 1. 找到最后一个元素的父节点的位置, (最后一个元素位置-1) / 2 int parent = (size-1-1) >>> 1; // 2. 判断k是否在父节点位置之后，如果在之前则需要下沉操作 while(k = (cap = (array = queue).length)) tryGrow(array, cap); try { Comparator

【本文地址】

公司简介

联系我们