java之优先级队列

PriorityQueue

案例

package com.kevin.container;

import java.util.PriorityQueue;
import java.util.Random;

public class PriorityQueueCase {

    public static void main(String[] args) {
        PriorityQueue priorityQueue = new PriorityQueue();
        int count = 10;
        for (int i = 0; i < count; i++) {
            priorityQueue.add(new Item());
        }

        while (!priorityQueue.isEmpty()) {
            System.out.println(priorityQueue.poll());
        }
    }
}

class Item implements Comparable<Item> {
    private int id;

    public Item(int id) {
        this.id = id;
    }

    public Item() {
        this.id = new Random().nextInt(100);
    }

    @Override
    public int compareTo(Item item) {
        return this.id - item.id;
    }

    @Override
    public String toString() {
        return "Item{" +
                "id=" + id +
                '}';
    }
}

源码解析

  • add

    • 优先级队列中维护有一个有序的Object 数组
    • 在向优先级队列添加元素时
      • 倒序遍历数组中的元素并和添加的对象进行比较
      • 如果当前元素比较后小于数组中该索引位置的元素,则将该索引的元素后置一位,并继续向前遍历
      • 当遍历到当前元素不小于索引位置元素时,记录位置,结束遍历,并将该对象保存至该索引位置
  • poll

    • 返回队列数组的第0索引位置上的元素
    • 如果返回元素后队列不为空,则将剩下的元素均前置一位

PriorityBlockingQueue

PriorityBlockingQueue priorityQueue = new PriorityBlockingQueue<>();

int count = 10;
for (int i = 0; i < count; i++) {
    priorityQueue.add(new Item());
}

while (!priorityQueue.isEmpty()) {
    System.out.println(priorityQueue.poll());
}
priorityQueue.poll();
System.out.println("end");
  • PriorityBlockingQueue与PriorityQueue基本一致
  • 区别为在add和poll等方法中添加了ReentrantLock锁,如果有其它线程竞争,则阻塞当前程序
  • 当队列为空时,再将poll,并不会阻塞,而会返回null