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

本文实例讲述了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());
  }
}

运行结果：

更多关于java算法相关内容感兴趣的读者可查看本站专题：《java数据结构与算法教程》、《java操作dom节点技巧总结》、《java文件与目录操作技巧汇总》和《java缓存操作技巧汇总》

希望本文所述对大家java程序设计有所帮助。