关于可排序队列PriorityBlockingQueue排序算法浅谈 |
您所在的位置：网站首页 › 队列排列整齐运用的数学依据是什么 › 关于可排序队列PriorityBlockingQueue排序算法浅谈 |
|
一直用队列没有去看底层实现 , 今天遇到个问题 , 遍历打印PriorityBlockingQueue时发现并没有按照既定的compareTo排序 , 以前用却从来没有发现过问题 , 抽空把它排序的底层实现看了看 以jdk1.8为例 PriorityBlockingQueue 排序时机划分为两处 插入 - put/add/offer 对应使用 siftUpComparable 排序方法； 每当加入一个元素 , 与当前队列队首元素compareTo比较 , 根据返回值决定是否排到队首弹出 - poll(remove)/take 对应使用 siftDownComparable 排序方法； 调用 dequeue 方法直接弹出队首元素 , 由于插入时保证队首永远为 compareTo 为1 的元素即符合判断顺序的元素 , siftDownComparable 方法使用建立最小堆的算法做元素重排序 , 排序细节参考http://www.sohu.com/a/165802088_355142 根据以上排序规则可得到 tasks.iterator() 遍历并不保证队列内顺序弹出元素保证顺序测试代码 private static class Task implements Comparable { public Integer id; public Task(String name, Integer id) { this.id = id; } public Integer getId() { return id; } public void setId(Integer id) { this.id = id; } @Override public String toString() { return "Task{" + "id=" + id + '}'; } @Override public int compareTo(Task task) { return task.id > this.id ? 1 :-1; } } public static void main(String[] args) { PriorityBlockingQueue tasks = new PriorityBlockingQueue(); Task task1 = new Task("task1", 5); Task task2 = new Task("task2", 2); Task task3 = new Task("task3", 3); Task task4 = new Task("task4", 3); Task task5 = new Task("task5", 23); Task task6 = new Task("task6", 8); Task task7 = new Task("task7", 0); tasks.add(task1); System.out.println(tasks); //[Task{id=5}] tasks.add(task2); System.out.println(tasks); //[Task{id=5}, Task{id=2}] tasks.add(task3); System.out.println(tasks); //[Task{id=5}, Task{id=2}, Task{id=3}] tasks.add(task4); System.out.println(tasks); //[Task{id=5}, Task{id=3}, Task{id=3}, Task{id=2}] tasks.add(task5); System.out.println(tasks); //[Task{id=23}, Task{id=5}, Task{id=3}, Task{id=2}, Task{id=3}] tasks.add(task6); System.out.println(tasks); //[Task{id=23}, Task{id=5}, Task{id=8}, Task{id=2}, Task{id=3}, Task{id=3}] tasks.add(task7); System.out.println(tasks); //[Task{id=23}, Task{id=5}, Task{id=8}, Task{id=2}, Task{id=3}, Task{id=3}, Task{id=0}] } |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |