优先级队列----堆优先级队列堆堆的创建堆的插入堆的删除PriorityQueue的特性PriorityQueue的构造与方法优先级队列

优先级队列

不同于先进先出的普通队列在一些情况下优先级高的元素要先出队列。

而这种队列需要提供两个基本的操作返回最高优先级对象

将一组集合的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中并满足Ki

K2i1

012…将根节点最大的堆叫做最大堆或大根堆根节点最小的堆叫做最小堆或小根堆。

例如

堆是一棵完全二叉树因此可以用层序的规则采用顺序的方式来高效存储但对于非完全二叉树就不适合使用顺序方式进行存储因为为了能够还原二叉树空间中必须要存储空节

表示孩子结点则父节点为

大则进行交换。

交换后可能会使原来满足堆的子树发生改变所以需要继续向下调整。

public

elem.length);}//放到最后一个位置长度加一elem[usedSize]

val;//向上调整shiftUp(usedSize-1);}public

boolean

tmp;//有效数据个数减一usedSize--;//向下调整shiftDown(0,

usedSize);}public

中放置的元素必须要能够比较大小不能插入无法比较大小的对象否则会抛出

ClassCastException

思路一我们可以初始化一个数组大小的堆然后遍历数组的同时将元素放进堆中默认是小根堆所以取

public

PriorityQueue(arr.length);//遍历数组

放进小根堆for

}上面这段代码会使时间复杂度升高每添加或删除一个元素就会调整一个接近数组长度的堆。

思路二要求最小

的大根堆因为是大根堆所以堆顶元素是堆中最大的元素然后遍历数组剩下的元素如果数组剩下的元素比堆顶元素小我们就删除堆顶元素并添加数组的元素如果数组剩下的元素比堆顶元素大它就不会是前

public

ret;}//提供比较器重写compare方法此时建立的就是大根堆QueueInteger

maxHeap

{maxHeap.offer(arr[i]);}//遍历数组未添加到堆中的元素for

(int

{//因为是求最小值所以如果比大根堆的堆顶元素小就删除堆顶元素并添加这个元素到堆中if

(arr[i]

{maxHeap.poll();maxHeap.offer(arr[i]);}}//将堆中的k个元素添加中数组中for

(int

个最大或最小的元素时数据少时我们可以排序但对于数据特别多时还是采用堆的方式比较合适。

步骤如下

N-K