MaxPQ

简书 賈小強
转载请注明原创出处，谢谢！

package com.lab1.test2;

public class MaxPQ<Key extends Comparable<Key>> {
    private Key[] a = (Key[]) new Comparable[2];
    private int n;

    private boolean isEmpty() {
        return n == 0;
    }

    private int size() {
        return n;
    }

    private Key delMax() {
        Key max = a[1];
        exch(1, n--);
        a[n + 1] = null;
        sink(1);
        if (n == (a.length - 1) / 4) {
            resize(a.length / 2);
        }
        return max;
    }

    private void sink(int k) {
        while (k * 2 <= n) {
            int j = k * 2;
            if (j < n && less(j, j + 1)) {
                j++;
            }
            if (less(k, j)) {
                exch(k, j);
            }
            k = j;
        }
    }

    private void resize(int capacity) {
        Key[] temp = (Key[]) new Comparable[capacity];
        for (int i = 0; i <= n; i++) {
            temp[i] = a[i];
        }
        a = temp;
    }

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

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

    private void put(Key key) {
        if (n == a.length - 1) {
            resize(a.length * 2);
        }
        a[++n] = key;
        swim(n);
    }

    private void swim(int k) {
        while (k > 1 && less(k / 2, k)) {
            exch(k / 2, k);
            k = k / 2;
        }
    }

    public static void main(String[] args) {
        MaxPQ<String> pq = new MaxPQ<>();
        pq.put("bill");
        pq.put("jack");
        pq.put("lucy");
        System.out.println(pq.delMax());
        System.out.println(pq.delMax());
        System.out.println(pq.delMax());
        System.out.println(pq.size());
        System.out.println(pq.isEmpty());
    }
}

输出

lucy
jack
bill
0
true

Happy learning !!