最大堆的优先队列

MaxPQ.java

package top.mollysu.type;

import java.util.Arrays;

/**
 * @author zmh
 * @date 2019-02-27 13:58
 * 优先队列
 * 删除最大元素，插入元素
 */
public class MaxPQ<Key extends Comparable<Key>> {

    private static final int DEFAULT_CAPACITY = 10;
    // pq[1..N]
    private Key[] pq;
    private int N;

    /**
     * 创建一个优先队列
     */
    public MaxPQ() {
        pq = (Key[]) new Comparable[DEFAULT_CAPACITY + 1];
    }

    /**
     * 创建一个初始容量为max的优先队列
     *
     * @param max 指定容量
     */
    public MaxPQ(int max) {
        pq = (Key[]) new Comparable[max + 1];
    }

    /**
     * @param a 用a[]中的元素创建一个优先队列
     */
    public MaxPQ(Key[] a) {

    }

    public static void main(String[] args) {
        MaxPQ<String> stringMaxPQ = new MaxPQ<>(20);
        String s = "EASYQUESTION";
        Arrays.stream(s.split("")).forEach(stringMaxPQ::insert);

        while (!stringMaxPQ.isEmpty()) {
            System.out.print(stringMaxPQ.delMax());
        }
    }


    /**
     * @return 根节点
     */
    public Key max() {
        return pq[1];
    }

    /**
     * 删除根节点的元素，并与数组的最后一个元素交换，减小堆大小并进行下沉操作
     *
     * @return 删除并返回最大元素
     */
    public Key delMax() {
        // 获取根节点
        Key max = pq[1];
        // 与最后一个结点交换
        exch(1, N);
        // 防止对象游离
        pq[N--] = null;
        // 下沉
        sink(1);
        return max;
    }

    /**
     * @return 返回队列是否为空
     */
    public boolean isEmpty() {
        return N == 0;
    }

    /**
     * @return 返回优先队列中的元素个数
     */
    public int size() {
        return N;
    }

    private boolean less(int i, int j) {
        return pq[i].compareTo(pq[j]) < 0;
    }

    private void exch(int i, int j) {
        Key t = pq[i];
        pq[i] = pq[j];
        pq[j] = t;
    }

    /**
     * 将新元素添加到数组尾部，增加堆大小并让这个新元素上浮到合适的位置
     *
     * @param v
     */
    public void insert(Key v) {
        pq[++N] = v;
        swim(N);
    }

    /**
     * 由下至上的堆有序化（上浮）
     *
     * @param k 结点
     */
    private void swim(int k) {
        while (k > 1 && less(k / 2, k)) {
            exch(k / 2, k);
            k /= 2;
        }
    }

    /**
     * 由下至上的堆有序化（下沉）
     *
     * @param k 结点
     */
    private void sink(int k) {
        while (2 * k <= N) {
            // 获取k结点的子节点之一
            int j = 2 * k;
            if (j < N && less(j, j + 1)) {
                // 获取子节点中较大者
                j++;
            }
            if (!less(k, j)) {
                // 如果子节点已经比结点更小，那么堆已经有序化，无需进行下面的交换操作
                break;
            }
            // 交换结点与子节点较大者的位置
            exch(k, j);
            k = j;
        }
    }
}