今天电话面试Oracle公司，面试官问了我这个问题，当然他当时是问在Java中ArrayList和LinkedList去作为实现
PriorityQueue的底层，那个更合适。
ArrayList约等于Vector嘛，我想了半天，也查了很久。
有个帖子是这么说的：
三、检索、插入、删除对象的效率
ArrayList和Vector中，从指定的位置（用index）检索一个对象，或在集合的末尾插入、删除一个对象的时间是一样的，可表示为O(1)。但是，如果在集合的其他位置增加或移除元素那么花费的时间会呈线形增长：O(n-i)，其中n代表集合中元素的个数，i代表元素增加或移除元素的索引位置。为什么会这样呢？以为在进行上述操作的时候集合中第i和第i个元素之后的所有元素都要执行(n-i)个对象的位移操作。
LinkedList中，在插入、删除集合中任何位置的元素所花费的时间都是一样的—O(1)，但它在索引一个元素的时候比较慢，为O(i),其中i是索引的位置。
所以，如果只是查找特定位置的元素或只在集合的末端增加、移除元素，那么使用Vector或ArrayList都可以。如果是对其它指定位置的插入、删除操作，最好选择LinkedList
可是我就更纠结了，以前用过数组去实现优先级队列，add元素的时候就要开始进行遍历式的对比（根据优先级），找到了位置之后，如果后面还有元素，那么后面的元素全部要向后位移一个位置（暂不考虑容量），优先级最高的自然在head咯，也就是数组0位置，那么在执行poll方法的时候就是：Retrieves and removes the head of this queue, or returns null if this queue is empty.返回并删除数组第一位嘛，刚才测试了java中的priorityqueue也是这样。
可我实在看不出vector比起LinkedList有啥优势啊？一个检索快，一个随机插入快，优先级比较的时候明明是在进行遍历的注意比较啊，你vector检索快有啥优势？返回的时候，又是返回第一个元素，我就纠结了，还是我理解错了？？？
求解释！谢谢~
------解决方案--------------------------------------------------------
>add元素的时候就要开始进行遍历式的对比（根据优先级）
说明你已经写挫了。logn可以写出来的东西你写线性……
堆（或者优先队列）本质上就是个二叉树，而最普通的堆的实现又可以用完全二叉树来实现。
既然用完全二叉树了，就可以用数组来存储这个完全二叉树，节点i的孩子是2*i和2*i+1。
链表怎么来存储这棵二叉树？
------解决方案--------------------------------------------------------
首先stl PriorityQueue 的实现 只是把vector当做默认容器而已 用其他的也可以
2L说的没错 数组可用索引位置来表示树结构关系 访问的时间复杂度是O(1) 如果用链表的话就慢很多了