为网站网站做网络维护,wordpress如何更换编辑器,江苏建设装饰集团有限公司,重庆发布的最新消息今天之前提高到队列是一种先进先出的结构#xff0c;但是在某些情况下操作的数据具有优先级#xff0c;那么对他先进行操作#xff0c;这时队列就不能满足需求了#xff0c;因为队列只能操作对头的元素#xff0c;而具有优先级的数据不一定是在对头#xff0c;这样就需要优先…之前提高到队列是一种先进先出的结构但是在某些情况下操作的数据具有优先级那么对他先进行操作这时队列就不能满足需求了因为队列只能操作对头的元素而具有优先级的数据不一定是在对头这样就需要优先级队列PriorityQueue了优先级队列能返回优先级高的数据添加新的对象
PriorityQueue的底层使用了堆这个数据结构
堆的概念
对于一个数据的集合1 2 3 4 5 6 7 8以完全二叉树的顺序储存方式储存在一起若根节点的值始终大于孩子节点堆叫做大根堆根节点小于孩子节点的叫做小根堆 以完全二叉树的储存方式储存的数据但是实际上储存在数组中在后面标上的下标可以得出
根节点 i 对应的子节点的下标 左节点 i * 2 1 右节点 i * 2 2 i为根节点的下标
堆的实现
字段设计 userSize记录有效数据的个数数组array储存数据
createHeap 创建堆 大根堆
向下调整 因为初始时的数组并不是一个堆那么就需要从最后开始堆他开始调整根据对应i 的左节点为 i*2 1右节点是i*22如果根节点小于子节点那么就和他进行交换若 i 的父节点J
若J右小于 i 交换后的值那么还需要进行交换小于就退出大于一直交换直到根节点结束 节点 i 对应父节点 (i-1)/2 左节点 (i*21) 右节点 (i*22)
每次进行向下调整交换的是左右节点最大的和根节点交换然后让节点 i 走到交换和他交换的子节点继续进行向下调整
将初始数组变为堆 向下调整 push 插入元素 向上调整
每次插入的位置是在useSize指向的下表位置然后从这个下标开始进行向上调整 创建的是大根堆 push 向上调整 poll 删除的是堆顶的元素
将堆顶元素和堆尾元素交换然后useSize--最后再最堆顶元素进行向下调整 peek 获得堆顶元素
直接返回0下标的数据就好 对于数据优先级这时放再堆顶的元素优先级就是最高的每次出出去的就是优先级最高的
再java中内置的优先级队列时PriorityQueue add 和offer俩方法都是一样的add会调用offer这个方法 对的使用
可以使用对来解决 top-k的问题找到k个最大的或者k个最小的数据
只需要先创建k个大小的优先级队列找最大的就是建小堆小的建大堆这时堆顶就是这个堆中最小的数据然后将要插入的元素和堆顶元素比较若大于堆顶就删除堆顶元素并插入元素 END
