算法 第二章第一部分笔记

很多情况下我们会收集一些元素，处理当前键值最大的元素，然后再收集更多的元素，再处理当前键值最大的元素，如此这般。这种情况下，一种合适的数据结构应该支持两种操作：删除最大元素和插入元素。这种数据类型叫做优先队列。
一种基于堆得优先队列简单实现方式

public class MaxPQ<Key extends Comparable<Key>> {
    private Key[] pq;
    private int N=0;
    public MaxPQ(int maxN){
        pq=(Key[])new Comparable[maxN+1];
    }

    public boolean isEmpty(){
        return N==0;
    }

    public int size(){
        return N;
    }

    public void insert(Key v){
        pq[++N]=v;
        swim(N);
    }

    public Key delMax(){
        Key max=pq[1];
        exch(1,N--);
        pq[N+1]=null;
        sink(1);
        StdOut.println("删除了"+max);
        return max;
    }

    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;
    }

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

    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){
        int M=5;
        MaxPQ<Transaction> pq=new MaxPQ<>(M+1);
        while(StdIn.hasNextLine()){
            pq.insert(new Transaction(StdIn.readLine()));

            if(pq.size()>M){
                pq.delMax();
            }
        }

        Stack<Transaction> stack=new Stack<Transaction>();
        while(!pq.isEmpty())stack.push(pq.delMax());
        for(Transaction t:stack) StdOut.println(t);
    }
}

索引优先队列

public class IndexMinPQ<Key extends Comparable<Key>> {

    private int N;
    private int[] pq;
    private int[] qp;
    private Key[] keys;

    public IndexMinPQ(int maxN) {
        N = 0;
        pq = new int[maxN + 1];
        qp = new int[maxN + 1];
        keys = (Key[]) new Comparable[maxN + 1];
        for (int i = 0; i <= maxN; i++) qp[i] = -1;
    }

    public void insert(int k, Key key) {

        if (contains(k)) throw new RuntimeException("item is already in pq");
        N++;
        qp[k] = N;
        pq[N] = k;
        keys[k] = key;
        swim(N);
    }

    public void change(int k, Key key) {
        if (!contains(k)) throw new RuntimeException("item is not in pq");
        keys[k] = key;
        swim(qp[k]);
        sink(qp[k]);
    }

    public boolean contains(int k) {
        return qp[k] != -1;
    }

    public void delete(int i) {
        if (i < 0 || i >= N) throw new IndexOutOfBoundsException();
        if (!contains(i)) throw new RuntimeException("index is not in the priority queue");
        int index = qp[i];
        exch(index, N--);
        swim(index);
        sink(index);
        keys[i] = null;
        qp[i] = -1;
    }

    public int delMin() {
        if (N == 0) throw new RuntimeException("Priority queue underflow");
        int min = pq[1];
        exch(1, N--);
        sink(1);
        assert min == pq[N + 1];
        qp[min] = -1;
        keys[min] = null;
        pq[N + 1] = -1;
        return min;

    }

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

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

    public boolean less(int i, int j) {
        return keys[pq[i]].compareTo(keys[pq[j]]) > 0;
    }

    public void exch(int i, int j) {
        int swap = pq[i];
        pq[i] = pq[j];
        pq[j] = swap;
        qp[pq[i]] = i;
        qp[pq[j]] = j;

    }

    public boolean isEmpty() {
        return N == 0;
    }

    public int size() {
        return N;
    }


    public static void main(String[] args) {
        // insert a bunch of strings
        String[] strings = {"it", "was", "the", "best", "of", "times", "it", "was", "the", "worst"};

        IndexMinPQ<String> pq = new IndexMinPQ<String>(strings.length);
        for (int i = 0; i < strings.length; i++) {
            pq.insert(i, strings[i]);
        }

        // delete and print each key
        while (!pq.isEmpty()) {
            int i = pq.delMin();
            StdOut.println(i + " " + strings[i]);
        }
        StdOut.println();

        // reinsert the same strings
        for (int i = 0; i < strings.length; i++) {
            pq.insert(i, strings[i]);
        }

        while (!pq.isEmpty()) {
            pq.delMin();
        }
    }
}