PriorityQueue 的 implementation

　　PriorityQueue即是优先队列。通俗的说就是体育课的时候老师要求从高到低排序，老师能直接一眼看出谁是最高的在班级里。当这个最高的离开的时候，老师也马上能知道下面哪个最高的人。

public class MaxPriorityQueue<T extends Comparable<T>> { 
public void insert(T t) {
 }
public T max(){}
public T delMax() {}
public boolean isEmpty() {}

public int size() {}
}

MaxPriorityQueue

　　具体实现的话有很多中，可以使用一个数组来存放所有的对象。每次delMax（删除最大的那个元素的时候）只需要遍历一遍数组找出最大的返回就可以了。这样子的话Time proportational to O(n), 时间是和n成正比的.

　　还有另外一种实现方法，是使用heap（堆结构），堆结构如下，可以清楚的知道堆的含义就是，顶层的元素的值比底层的大。一级压一级。

　　堆一般用数组来实现，从index=1开始（方便计算）,index * 2 和 index * 2 + 1 就是左右子元素， index / 2 就是父元素

　　好了，现在假设你有这样子的一个堆

　　现在我要插入一个111，我先把111 插入到底部

　　这个时候破坏了heap的有序，堆有序需要底部的元素小于顶部，所以我们把111 和 111的顶部（以后我会叫parentNode）进行比较

　　发现111大于33，所有我需要改变exchange 111 和 33的位置

　　接着111 和 parentNode比，发现还是大于ParentNode，所以继续改变位置。

　　继续比较

　　到了top了，没有元素比111大了。堆又有序了。每次堆因为插入或者删除造成的无须都可以用这样子的操作来挽回。

　　接着说如何删除一个最大的元素。比如刚才的那个堆，我们要拿到最大的那个元素。

　　首先我们先把111和最底部的元素交换位置。并且取出111

　　现在堆的有序被破坏了。我们要把top部的元素和2个子元素比较大小，如果比子元素小的话，外面就需要交换他们的位置

　　在这里，我们需要把33 和 100 和 50 比较。把值小的元素放在堆底部。把33 和 Math.max（100， 50）交换位置得到如下

　　33 比 90 小。交换他们的位置

　　这个时候堆又有序了。

Are u Okay

　　堆的有序性必须得到保证。

　　每次的插入insert（）和 delMax（）的操作所需要的时间与 Log（N）成正比。O(logN)

　　具体的实现可以参考一下https://github.com/Cheemion/algorithms/blob/master/src/com/algorithms/elementary/MaxPriorityQueue.java

　　每个人的实现都不一样。

秒客网

PriorityQueue 优先队列的实现

PriorityQueue 的 implementation

相关文章