资讯

精准传达 • 有效沟通

从品牌网站建设到网络营销策划,从策略到执行的一站式服务

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

本文实例讲述了Java基于堆结构实现优先队列功能。分享给大家供大家参考,具体如下:

成都创新互联主要从事网站建设、网站设计、网页设计、企业做网站、公司建网站等业务。立足成都服务农安,10多年网站建设经验,价格优惠、服务专业,欢迎来电咨询建站服务:18980820575

package Demo;
import java.util.NoSuchElementException;
/*
 * 小顶堆 java使用堆结构实现优先队列
 */
public class JPriorityQueue {
  @SuppressWarnings("hiding")
    class QueueNode {
    int capacity;
    int size;
    E[] queue;
    QueueNode(int capacity) {
      this.capacity = capacity;
    }
  }
  QueueNode node;
  public void print()
  {
    E[] objs=this.node.queue;
    for(int i=0;i(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 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 queue = new JPriorityQueue(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数据结构与算法教程》、《Java操作DOM节点技巧总结》、《Java文件与目录操作技巧汇总》和《Java缓存操作技巧汇总》

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


网页题目:Java基于堆结构实现优先队列功能示例
网站地址:http://www.cdkjz.cn/article/gedpes.html
多年建站经验

多一份参考,总有益处

联系快上网,免费获得专属《策划方案》及报价

咨询相关问题或预约面谈,可以通过以下方式与我们联系

大客户专线   成都:13518219792   座机:028-86922220