集册 Java实例教程 实现在最小键上迭代的无序优先级队列。

实现在最小键上迭代的无序优先级队列。

欢马劈雪     最近更新时间:2020-01-02 10:19:05

230
实现在最小键上迭代的无序优先级队列。
/**时代Java公众号**/

import static java.lang.System.out;


import java.util.NoSuchElementException;



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


    private Key[] pq;

    private int N;

    

    public UnorderedMinPQ() {

      this(1);

    }

    
    /*
    nowjava.com - 时  代  Java
    */

    @SuppressWarnings("unchecked")    

    public UnorderedMinPQ(int capacity) {

        pq = (Key[]) new Comparable[capacity];

    }

      

    public boolean isEmpty() {

        return N == 0;

    }

    

    public void insert(Key k) {

      if (N == pq.length - 1) 

          resize(2 * pq.length);

      

        pq[N++] = k;

    }

    

    public Key delMin() {

      if (isEmpty()) 

          throw new NoSuchElementException();

      

        int min = 0;

        for (int i = 1; i < N; i++)

            if (less(i, min))

                min = i;

        

        exch(min, N-1);

        Key k = pq[--N];

        pq[N] = null;

        

        if ((N > 0) && (N == (pq.length - 1) / 4)) 

            resize(pq.length  / 2);

        

        return k;

    }

    

    private boolean less(int i, int j) {

      return pq[i].compareTo(pq[j]) < 0;

    }

    

    private void exch(int i, int j) {

        Key swap = pq[i];

        pq[i] = pq[j];

        pq[j] = swap;

    }

    

    private void resize(int capacity) {

        @SuppressWarnings("unchecked")

        Key[] copy = (Key[]) new Comparable[capacity];

        

        for (int i = 0; i <= N; i++) 

            copy[i] = pq[i];

        

        pq = copy;

    }

    

    public static void main(String[] args) {

      UnorderedMinPQ<String> queue = new UnorderedMinPQ<String>();

        queue.insert("P");

        queue.insert("R");

        queue.insert("I");

        queue.insert("O");

        queue.insert(
展开阅读全文