1. 内容大纲

本章节代码：https://github.com/wicksonZhang/data-structure/tree/main/13-PriorityQueue

优先级队列

2. 优先级队列是什么?

优先级队列: 优先级队列也是队列的一种, 但是优先级队列 没有遵循普通队列的 FIFO(先进先出) 原则, 而是按照 优先级高低 进行出队.

  • 例如, 下图中的元素 44 虽然在队尾, 但是可以让元素 44 第一个出来.

image-20240206141415049

3. 接口设计

  • 优先级队列的接口还是和队列的接口保持一致.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * 优先级队列
 *
 * @author ZhangZiHeng
 * @date 2024-02-06
 */
public class PriorityQueue<E> {

    // 元素的数量
    public int size(){}

    // 是否为空
    public boolean isEmpty(){}

    // 清空元素
    public void clear() {}
        
    // 入队
    public void enQueue(E element){}

    // 出队
    public E deQueue(){}

    // 获取队列的头元素
    public E front(){}

}

4. 代码实现

4.1. 成员初始化

  • 我们由于队列需要具备可比较性并且需要每次出队时需要将最大元素出队, 所以采用 二叉堆 实现优先级队列.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * 优先级队列
 *
 * @author ZhangZiHeng
 * @date 2024-02-06
 */
public class PriorityQueue<E> {

    private final BinaryHeap<E> binaryHeap;

    public PriorityQueue() {
        this(null);
    }

    public PriorityQueue(Comparator<E> comparator) {
        this.binaryHeap = new BinaryHeap<>(comparator);
    }
    
}

4.2. 元素的数量

1
2
3
4
5
6
7
8
9
   /**
    * 元素的数量
    *
    * @return int
    */    
@Override
   public int size() {
       return binaryHeap.size();
   }

4.3. 是否为空

1
2
3
4
5
6
7
8
9
   /**
    * 是否为空
    *
    * @return boolean
    */
@Override
   public boolean isEmpty() {
       return binaryHeap.isEmpty();
   }

4.4. 清空元素

1
2
3
4
5
6
7
   /**
    * 清空元素
    */
@Override
   public void clear() {
       binaryHeap.clear();
   }

4.5. 入队

1
2
3
4
5
6
7
8
/**
 * 入队
 *
 * @param element 元素
 */
public void enQueue(E element) {
    binaryHeap.add(element);
}

4.6. 出队

1
2
3
4
5
6
7
8
/**
 * 出队
 *
 * @return E
 */
public E deQueue() {
    return binaryHeap.remove();
}

4.7. 获取队列的头元素

1
2
3
4
5
6
7
8
/**
 * 获取队列的头元素
 *
 * @return E
 */
public E front() {
    return binaryHeap.get();
}

4.8. 单元测试

我们创建一个对象 Person 比较字段的大小

  • Person.java 对象
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Person implements Comparable<Person> {

    private String name;

    private int boneBreak;

    public Person(String name, int boneBreak) {
        this.name = name;
        this.boneBreak = boneBreak;
    }

    @Override
    public String toString() {
        return "Person{" +
                "name='" + name + '\'' +
                ", boneBreak=" + boneBreak +
                '}';
    }

    @Override
    public int compareTo(Person person) {
        return this.boneBreak - person.boneBreak;
    }
}
  • 测试
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class PersonTest {

    @Test
    public void test() {
        PriorityQueue<Object> queue = new PriorityQueue<>();
        queue.enQueue(new Person("jack" , 1));
        queue.enQueue(new Person("tom" , 2));
        queue.enQueue(new Person("rose" , 3));
        queue.enQueue(new Person("tim" , 4));
        queue.enQueue(new Person("jerry" , 5));
        queue.enQueue(new Person("Jim" , 6));
        while (!queue.isEmpty()) {
            System.out.println(queue.deQueue());
        }
    }

}
  • 结果
1
2
3
4
5
6
Person{name='Jim', boneBreak=6}
Person{name='jerry', boneBreak=5}
Person{name='tim', boneBreak=4}
Person{name='rose', boneBreak=3}
Person{name='tom', boneBreak=2}
Person{name='jack', boneBreak=1}

5. 参考博文