java数据结构---堆结构PriorityQueue

PriorityQueue本身的逻辑结构是一棵完全二叉树，而它的存储结构是一个数组。因为完全二叉树层次遍历的结果刚好是一个数组。

 

层次遍历之后的结果:

 

PriorityQueue的操作 :

(1)add(E e)和offer(E e):

源码:

add()还是调用的offer()方法;

在offer方法中grow()目的为的是扩容;如果queue队列中没有值,就直接放到第一个里面,如果有值则调用siftUp()方法;

 当你没有自定义comparator(序列化)的时候,就会调用siftUpComparable(),如果没有传入的话,基本上都是以从小到大的顺序对队列中的值进行排序.

进入siftUpComaprable():

这段代码的意思就是,在队列中一直往上找,key值小于当前值的就替换掉;

我还是在这解释一下,网上很多博客对这里的解释有问题:

进入bq.add(2)->

由于queue当前为空,所以直接放入到第一个节点上;

 

 

 

由于我们没有自定义序列化,所以调用后面这个默认的系列化,也就是从小到大排序(后面你就知道为什么是从小到大了):

 

 所以应该可以知道了吧,逻辑就是跟前面的节点进去比较,如果大的话就放到后面,小的放前面;

现在 queue里面的数据{2,5}

继续往下:

 

 

看到没.这就是核心,它将大于key的值全部调换位置放到后面,然后继续往上找,找到找到小于key 的值之后,退出循环,然后赋值给k位置(因为在前一次已经替换了,所以是空位置,直接放).后面我就不在分析了,最后和2调换位置,放到头位置那里了;

(2)poll() 和 remove() 方法 

poll 方法每次从 PriorityQueue 的头部删除一个节点，也就是从小顶堆的堆顶删除一个节点，而remove（）不仅可以删除头节点而且还可以用 remove(Object o) 来删除堆中的与给定对象相同的最先出现的对象。

了解一下poll()方法:

poll（）方法的源码:

这里还是挺好理解的,我就不细说了,思想就是取出头结点的值和尾节点的值,并且令尾节点为空,主要是看siftDown()方法:

 

siftDown（）方法就是从堆的第一个元素往下比较，如果比左右孩子节点的最小值小则与最小值交换，交换后继续向下比较，否则停止比较。  

remove的代码： 

无参,和poll()一样:

有参:

 

 

remove()和poll（）函数一样，只不过poll（）函数每次都是从堆顶开始。