首页 / JAVA / Java笔记(十)堆与优先级队列
Java笔记(十)堆与优先级队列
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了Java笔记(十)堆与优先级队列,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2524字,纯文字阅读大概需要4分钟。
内容图文
优先级队列
一、PriorityQueue
PriorityQueue是优先级队列,它实现了Queue接口,它的队列长度
没有限制,与一般队列的区别是,它有优先级概念,每个元素都有优先
级,队头的元素永远都是优先级最高的。PriorityQueue内部是用堆实现的。
一、基本用法
主要构造方法:
public PriorityQueue() public PriorityQueue(int initialCapacity, Comparator<? super E> comparator) public PriorityQueue(Collection<? extends E> c) //动态数组大小等于容器中元素的个数
PriorityQueue使用动态数组initialCapacity表示初始数组的大小。举例:
PriorityQueue<Integer> ints = new PriorityQueue<>(); ints.offer(10); ints.add(28); ints.addAll(Arrays.asList(22, 33, 55, 66)); while (ints.peek() != null) { System.out.println(ints.poll() + " "); }
二、实现原理
内部成员:
private transient Object[] queue; private int size = 0; private final Comparator<? super E> comparator; private transient int modCount = 0;
构造方法:
public PriorityQueue() { this(DEFAULT_INITIAL_CAPACITY, null); } public PriorityQueue(int initialCapacity) { this(initialCapacity, null); } public PriorityQueue(int initialCapacity, Comparator<? super E> comparator) { if(initialCapacity < 1) throw new IllegalArgumentException(); this.queue = new Object[initialCapacity]; this.comparator = comparator; }
添加元素的代码
public boolean offer(E e) { if(e == null) throw new NullPointerException(); modCount++; int i = size; if(i >= queue.length) //先确保数组长度是否足够,如果不够,用grow方法扩展? grow(i + 1); size = i + 1; if(i == 0) //如果是第一次添加 queue[0] = e; else //否则将其放入最后一个位置,并向上调整 siftUp(i, e);return true; }
private void grow(int minCapacity) { int oldCapacity = queue.length; // Double size if small; else grow by 50% int newCapacity = oldCapacity + ((oldCapacity < 64) (oldCapacity + 2) : (oldCapacity >> 1)); // overflow-conscious code if(newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); queue = Arrays.copyOf(queue, newCapacity); }
private void siftUp(int k, E x) { if(comparator != null) siftUpUsingComparator(k, x); else siftUpComparable(k, x); }
private void siftUpUsingComparator(int k, E x) { while(k > 0) { int parent = (k - 1) >>> 1; Object e = queue[parent]; if(comparator.compare(x, (E) e) >= 0) break; queue[k] = e; k = parent; } queue[k] = x; }
查看元素头部元素:
public E peek() { if(size == 0) return null; return (E) queue[0]; }
删除头部元素:略
三、总结
1)实现了优先级队列,最先出队的总是优先级最高的,即排序中的第一个。
2)优先级可以有相同的,内部元素不是完全有序的,如果遍历输出,除了第一个其他没有特定顺序。、
3)查看头部元素,入队出队的效率都很高
4)根据值查找和删除元素的效率很低。
内容总结
以上是互联网集市为您收集整理的Java笔记(十)堆与优先级队列全部内容,希望文章能够帮你解决Java笔记(十)堆与优先级队列所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。