Java最大优先队列设计与实现

Java 学习+面试指南：https://javaxiaobear.cn

1、API设计

类名	MaxPriorityQueue
构造方法	MaxPriorityQueue(int capacity)：创建容量为capacity的MaxPriorityQueue对象
成员方法	private boolean less(int i,int j)：判断堆中索引i处的元素是否小于索引j处的元素 private void each(int i,int j):交换堆中i索引和j索引处的值 public T delMax():删除队列中最大的元素,并返回这个最大元素 public void insert(T t)：往队列中插入一个元素 private void swim(int k):使用上浮算法，使索引k处的元素能在堆中处于一个正确的位置 private void sink(int k):使用下沉算法，使索引k处的元素能在堆中处于一个正确的位置 public int size():获取队列中元素的个数 public boolean isEmpty():判断队列是否为空
成员变量	private T items：用来存储元素的数组 private int N：记录堆中元素的个数

2、代码实现

public class MaxPriorityQueue<T extends Comparable<T>> {private T[] items;private int size;public MaxPriorityQueue(int capacity){items = (T[]) new Comparable[capacity + 1];size = 0;}/*** 判断堆中索引i处的元素是否小于索引j处的元素* @param i* @param j* @return true*/private boolean less(int i,int j){return items[i].compareTo(items[j]) < 0;}/*** 交换堆中i索引和j索引处的值* @param i* @param j*/private void each(int i,int j){T temp = items[i];items[i] = items[j];items[j] = temp;}/*** 删除队列中最大的元素,并返回这个最大元素* @return*/public T delMax(){T max = items[1];each(1,size);items[size] = null;size--;sink(1);return max;}/*** 往队列中插入一个元素* @param t*/public void insert(T t){items[++size] = t;swim(size);}/*** 使用上浮算法，使索引k处的元素能在堆中处于一个正确的位置* @param k*/private void swim(int k){while (1 < k){//比较k是否小于k/2，如果小于则交换元素if(less(k/2,k)){each(k/2,k);}k = k/2;}}/*** 使用下沉算法，使索引k处的元素能在堆中处于一个正确的位置* @param k*/private void sink(int k){while (2 * k <= size){int max = 2 * k;//如果存在右子结点if(2 * k + 1 <= size){if(less(2*k,2*k+1)){max = 2 * k + 1;}}//比较当前结点和子结点中的较大者，如果当前结点不小，则结束循环if(!less(k,max)){break;}each(k,max);k = max;}}/*** 获取队列中元素的个数* @return*/public int size(){return size;}/*** 判断队列是否为空* @return*/public boolean isEmpty(){return size == 0;}
}

• 测试类

  public class MaxPriorityQueueTest {public static void main(String[] args) {String[] arr = {"A", "B", "C", "D", "E", "F", "G"};MaxPriorityQueue<String> queue = new MaxPriorityQueue(10);for (String s : arr) {queue.insert(s);}System.out.println(queue.size());String max;while (!queue.isEmpty()){max = queue.delMax();System.out.print(max+ " ");}}
  }
  

  输出结果

  7
  G F E D C B A