Java基于堆结构实现优先队列功能示例

package Demo;import java.util.NoSuchElementException;/* * 小顶堆 java使用堆结构实现优先队列 */public class JPriorityQueue<E> {  @SuppressWarnings("hiding")    class QueueNode<E> {    int capacity;    int size;    E[] queue;    QueueNode(int capacity) {      this.capacity = capacity;    }  }  QueueNode<E> node;  public void print()  {    E[] objs=this.node.queue;    for(int i=0;i<this.node.size;i++)    {      System.out.print(objs[i]+" ");    }    System.out.println();  }  @SuppressWarnings("unchecked")    public JPriorityQueue(int capacity) {    node = new QueueNode<E>(capacity);    node.size = 0;    node.queue = (E[]) new Object[capacity + 1];  }  public void add(E x) {    int k = node.size;    while (k > 0) {      int parent = (k - 1) / 2;      E data = node.queue[parent];      @SuppressWarnings({ "unchecked", "rawtypes" })      Comparable<E> key = (Comparable) x;      if (key.compareTo(data) >= 0)        break;      node.queue[k] = data;      k = parent;    }    node.queue[k] = x;    node.size++;  }  public E remove() {    int parent = 0;    if (node.size == 0) {      throw new NoSuchElementException("queue is null");    }    E min = node.queue[0];// top    E last = node.queue[node.size - 1];// last    node.queue[0] = last;// add the last to top    node.queue[node.size - 1] = null;    node.size--;    @SuppressWarnings("unchecked")    Comparable<? super E> complast = (Comparable<? super E>) last;    if (node.size == 2 && complast.compareTo(node.queue[1]) > 0) { // 只剩下最后两个结点，进行比较      node.queue[0] = node.queue[1];      node.queue[1] = last;    }    if (node.size > 2) { // 大于三个结点的，向下旋转      while (parent < node.size / 2) {        int left = 2 * parent + 1;// left child        int right = left + 1;// right child        E root = node.queue[parent];        @SuppressWarnings("unchecked")        Comparable<? super E> comproot = (Comparable<? super E>) root;        if (comproot.compareTo(node.queue[left]) < 0          && comproot.compareTo(node.queue[right]) < 0)          break;        @SuppressWarnings("unchecked")        Comparable<? super E> compleft = (Comparable<? super E>) node.queue[left];        if (compleft.compareTo(node.queue[right]) <= 0) {          node.queue[parent] = node.queue[left];          node.queue[left] = root;          parent = left;        } else {          node.queue[parent] = node.queue[right];          node.queue[right] = root;          parent = right;        }        if (right * 2 >= node.size)          break;      }    }    return min;  }  public static void main(String[] args) {    System.out.println("武林网测试结果：");    JPriorityQueue<String> queue = new JPriorityQueue<String>(10);    queue.add("Z");    queue.add("B");    queue.add("QZA");    queue.add("QBA");    queue.add("EAA");    queue.add("A");    queue.print();    // queue.remove();    // queue.remove();    // queue.remove();    // queue.remove();    // queue.remove();    System.out.println(queue.remove());    System.out.println(queue.remove());    System.out.println(queue.remove());    System.out.println(queue.remove());    System.out.println(queue.remove());    System.out.println(queue.remove());  }}