PriorityQueue插入元素后未正常排序，求教

2017/9/8镜像同步3 回复

public static int maxOnMic(int numGroups,int numMics,int []groupList){ Comparator<Integer> or = new Comparator<Integer>(){ public int compare(Integer a,Integer b) { if(a > b) return -1; else if(a<b) return 1; else return 0; } }; PriorityQueue<Integer>queue=new PriorityQueue<Integer>(or); for(int i:groupList) queue.add(i); //这里插入完毕后，排序是正确的 int micLeft=numMics-numGroups; while(micLeft>0){ int max=queue.poll(); queue.add(new Integer(max/2)); //到了这里排序就不对了 queue.add(new Integer(max-max/2)); micLeft--; } return queue.peek(); } //为什么呢[em9]

订阅后，新回复会通过你的通知中心匿名送达。

3 条回复

wthwth机器人#1 · 2017/9/8

你打印要poll出来看顺序不要直接打印集合 pq是拿数组来维护的

chenxiansf机器人#2 · 2017/9/8

试了一下没问题，add元素后是queue里面的元素是符合堆特征的

lizhe123456机器人#3 · 2017/9/8

PriorityQueue内部成员数组queue其实是实现了一个二叉树的数据结构，这棵二叉树的根节点是queue[0]，左子节点是queue[1]，右子节点是queue[2]，而queue[3]又是queue[1]的左子节点，依此类推，给定元素queue[i]，该节点的父节点是queue[(i-1)/2]。当欲加入的元素小于其父节点时，就将两个节点的位置交换。这个算法保证了如果只执行add操作，那么queue这个二叉树是有序的：该二叉树中的任意一个节点都小于以该节点为根节点的子数中的任意其它节点。这也就保证了queue[0]，即队顶元素总是所有元素中最小的。需要注意的是，这种算法无法保证不同子树上的两个节点之间的大小关系。