JAVA源码阅读之PriorityQueue

刷题时偶尔看到别人的答案里会用到这种类PriorityQueue，主要功能就是用了这个类输出时就是按照队列中的元素排序来输出。比Arrays.sort()不知道高到哪里去了。同样我们在生成实例时也能够自定义比较函数从而使它的排序完全符合我们的要求。比如按照二进制表示中1的数量来进行排序。还是挺强大的。。
这个类整体是用一个二叉小顶堆实现的，用完全二叉数来表示。主要属性是

• 两个子节点都大于等于他们的父亲节点。

• 只有最下面的两层结点度能够小于2，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树。
  而代码中的具体实现是一个Object类型的数组，数组的名字、叫队列（要不怎么叫PriorityQueue呢？）于是我们再回来理解一下性质2，说明所有的元素都处于queue的左侧。这样排列能够实现通过数组下标来计算出每个节点的父亲节点和左右子节点！！

  
  

每个节点的父亲节点：（index-1）/2

每个节点的左节点：index*2+1

每个节点的右节点：index*2+2

大家可以试一试上面这个性质

盗图还是蛮紧张的

（int）size来记录队列中元素的个数
在这里add(E e)和offer(E e)是一样的

首先对于null元素会throw

当目前的元素数目大于当前队列的容量，会使用grow函数来扩容。跳过这个环节的话如果当前队列里没有元素就添加为第一个元素，或者使用siftup先试图添加到末尾再进行调整。siftup方法中会考虑使用的比较器是否为默认比较器。。再分别调用siftUpComparable（默认）或者siftUpUsingComparator（自定义）。。我就分析一个默认的吧

k表示插入位置，x表示要插入的元素
第一行的key表示将元素x转换为Comparable类型的变量，之后再不断将key与x的父亲节点比较，小于它时根据小根堆的性质需要将元素x上移，父亲节点下移，直到当前元素大于其父亲节点或遍历至队头。插入完成。
再分析一个removeAt方法吧。remove()和removeAt()都是用到了它，但是这种不加修饰的方法包外并不能访问，其次虽然它的返回类型是E，但是调用它的方法，返回类型都是boolean。。直接调用remove和removeAt也不会用到它的返回值，但是在实现了Iterator的类Itr中会用到。我这里就先不考虑它的返回值能够做什么了。

如果恰好要remove掉最后一个元素，那就无所谓了，不影响父子节点比大小，也不影响性质2，还是一个完全二叉树。
sitfDown的输入为所要删除的点与堆的最后一个元素。小根堆在删除元素时一般将最后元素放置在被删除置为空的位置。在siftDownComparable或siftDownUsingComparator中判断当所要删除的节点为叶子节点时，将末尾元素置于此肯定满足小根堆子节点大于父亲节点的性质。（一次性满足时符合queue[i] == moved，此时有可能不满足该节点的值小于其父亲节点，故需要再进行siftUp来更改结构）。当要删除的节点不为叶子节点时，将moved元素与相对小的孩子节点比较。若能够满足小根堆性质则进行赋值（一次性满足时符合queue[i] == moved，此时有可能不满足该节点的值小于其父亲节点，故需要再进行siftUp来更改结构），否则继续向下寻找。

写文章果然还是一气呵成比较好。。再翻出来写思路结构都不是很统一了。。

重要参考 http://www.importnew.com/20169.html