`
- 浏览:
23386 次
- 性别:
- 来自:
珠海
-
package kitsion.util;
/**
* PriorityQueue class implemented via the binary heap.
*/
public class PriorityQueue<AnyType> extends AbstractCollection<AnyType>
implements Queue<AnyType> {
public PriorityQueue() {
currentSize = 0;
cmp = null;
array = (AnyType[]) new Object[DEFAULT_CAPACITY + 1];
}
/**
* Construct an empty PriorityQueue with a specified comparator
*
* @param c
*/
public PriorityQueue(Comparator<? super AnyType> c) {
currentSize = 0;
cmp = c;
array = (AnyType[]) new Object[DEFAULT_CAPACITY + 1];
}
/**
* Construct a PriorityQueue from another Collection
*
* @param coll
*/
public PriorityQueue(Collection<? extends AnyType> coll) {
cmp = null;
currentSize = coll.size();
array = (AnyType[]) new Object[(currentSize + 2) * 11 / 10];
int i = 1;
for (AnyType item : coll)
array[i++] = item;
buildHeap();
}
/**
* Returns the number of items in this PriorityQueue
*/
public int size() {
return currentSize;
}
public void clear() {
currentSize = 0;
}
/**
* Returns an iterator over the elements in this PriorityQueue
*/
public Iterator<AnyType> iterator() {
return new Iterator<AnyType>() {
int current = 0;
public boolean hasNext() {
return current != size();
}
public AnyType next() {
if (hasNext())
return array[++current];
else
throw new NoSuchElementException();
}
public void remove() {
throw new UnsupportedOperationException();
}
};
}
/**
* Returns the smallest item in the priority queue
*/
public AnyType element() {
if (isEmpty())
throw new NoSuchElementException();
return array[1];
}
/**
* Adds an item to this PriorityQueue.
*/
public boolean add(AnyType x) {
if (currentSize + 1 == array.length)
doubleArray();
/* 详细注解: 增加堆的当前大小,并设置空结点为新增加的结点 */
int hole = ++currentSize;
/* 详细注解: 把x作为负无穷标志,放入位置0 */
array[0] = x;
/* 详细注解: 只要父结点中的项大于x,重复执行向上过滤的策略,指将父结点中的项下移到空结点中,然后将空结点上移到父结点 */
for (; compare(x, array[hole / 2]) < 0; hole /= 2)
array[hole] = array[hole / 2];
array[hole] = x;
return true;
}
/**
* Removes the smallest item in the priority queue.
*/
public AnyType remove() {
AnyType minItem = element();
array[1] = array[currentSize--];
percolateDown(1);
return minItem;
}
/**
* 详细注解: percolateDown的一个参数指示空结点的位置,然后空结点中项被移出,开台向下过滤,
* 当没有左孩子,循环结束,因为偶数大小的堆里的最后一个结点是仅有一个子结点,所以还要在向下过滤 中,进行测试.
*
* @param hole
*/
public void percolateDown(int hole) {
int child;
AnyType tmp = array[hole];
for (; hole * 2 <= currentSize; hole = child) {
child = 2 * hole;
if (child != currentSize
&& compare(array[child + 1], array[child]) < 0)
child++;
if (compare(array[child], tmp) < 0)
array[hole] = array[child];
else
break;
}
array[hole] = tmp;
}
/**
* 逆序采用向下过滤策略,构造有序堆
*/
public void buildHeap() {
for (int i = currentSize / 2; i > 0; i--)
percolateDown(i);
}
// number of elements in heap
private int currentSize;
// The heap array
private AnyType[] array;
private Comparator<? super AnyType> cmp;
private static final int DEFAULT_CAPACITY = 100;
/**
* Internal method to extend array
*/
private void doubleArray() {
AnyType[] newArray;
newArray = (AnyType[]) new Object[array.length * 2];
for (int i = 0; i < array.length; i++)
newArray[i] = array[i];
array = newArray;
}
/**
* Compares lhs and rhs using comparator if provided by cmp, or the default
* comarator
*
* @param lhs
* @param rhs
* @return
*/
private int compare(AnyType lhs, AnyType rhs) {
if (cmp == null)
return ((Comparable) lhs).compareTo(rhs);
else
return cmp.compare(lhs, rhs);
}
}
分享到:
Global site tag (gtag.js) - Google Analytics
相关推荐
"priority_queue_1.0_excitingfbh_matlab优先队列_matlab优先队列_优先队列_"这个标题表明这是一个MATLAB环境下的优先队列实现,可能由excitingfbh开发者创建,版本为1.0。 描述中提到的"pq_create"是创建优先队列...
优先队列在Java编程中是一种特殊的数据结构,它遵循特定的出队顺序,通常是最小元素(最小优先队列)或最大元素(最大优先队列)先出队。这种数据结构在解决各种问题时非常有用,例如任务调度、事件驱动编程、搜索...
优先队列是一种特殊的数据结构,它允许我们按照优先级顺序处理元素。在计算机科学中,尤其是在算法和数据结构领域,优先队列常用于解决需要快速访问最高优先级元素的问题,如Dijkstra算法或Prim算法。在C语言中,...
优先队列是一种特殊的队列,它的主要特性是队首元素具有最高的优先级。在Java中,我们可以使用数组来实现优先队列。这篇文章将探讨如何利用数组实现优先队列,并通过提供的`PriorityQ.java`文件来深入理解其实现原理...
根据给定文件的信息,我们可以详细地...通过上述分析,我们可以看出最大优先队列和最小优先队列在实现上的相似性和差异性,以及它们各自的应用场景。希望以上内容能够帮助您更好地理解优先队列的基本概念和实现细节。
队列是一种先进先出(FIFO)的数据结构,而优先队列则在此基础上增加了优先级的概念。Java中的`Queue`接口提供了基本的队列操作,如`offer()`(添加元素)、`peek()`(查看但不移除首元素)和`poll()`(移除并返回首...
综上所述,优先队列是算法设计中的重要工具,Java中的PriorityQueue类提供了方便的接口,但自定义实现有助于深入理解和优化。在实际应用中,理解其内部工作机制以及如何适配具体需求是非常关键的。通过阅读和分析...
优先队列是一种特殊的数据结构,它允许我们根据元素的优先级进行操作,通常用于处理具有紧急程度的任务。在这个实验报告中,优先队列是通过最大堆实现的,最大堆是一种完全二叉树,其中每个父节点的优先权重都大于或...
优先队列(Priority Queue)是数据结构中的一种特殊队列,它的主要特点是元素的出队顺序不是按照“先进先出”(FIFO)的原则,而是根据每个元素的优先级来决定。这种数据结构广泛应用于各种算法和系统设计中,如事件...
C语言优先队列 C语言优先队列是一种特殊的队列结构,它允许元素按照一定的优先权顺序排列。在本实现中,我们使用堆来实现优先队列的存储和排序。 知识点一:堆数据结构 堆是一种特殊的树形数据结构,它满足以下两...
"STL优先队列、队列、栈" STL(Standard Template Library)中的优先队列、队列、栈是三个非常重要的数据结构,它们在实际应用中有着广泛的应用。本文将详细介绍STL中的优先队列、队列、栈,包括它们的定义、操作、...
优先队列是一种特殊的数据结构,它在队列的基础上增加了优先级的概念。在传统的队列中,元素遵循“先进先出”(FIFO)的原则,但优先队列则根据每个元素的优先级决定出队顺序,优先级高的元素会比优先级低的元素更早...
优先队列、图等总结及习题 优先队列是一种特殊的队列结构,它的出队顺序是根据元素的优先权决定的,而不是元素入队的顺序。优先队列的操作包括查找、插入和删除,删除操作是根据优先权高或低的次序进行的。 一、...
3. **广泛应用前景**:由于堆实现的优先队列在时间和空间上的优异表现,它可以在各种计算机排队算法中得到推广和应用,比如在网络路由、资源分配等领域。 #### 堆实现优先队列的关键技术 - **插入操作**:当向优先...
在IT领域,多级优先队列(Multi-Level Priority Queues)是一种重要的数据结构,尤其在操作系统设计中扮演着核心角色。这种数据结构允许我们高效地处理具有不同优先级的任务,通常用于调度算法,如进程调度或任务...
优先队列是一种特殊的数据结构,它允许我们按照优先级处理元素。在计算机科学中,特别是在算法和数据结构领域,优先队列通常用于实现任务调度、事件驱动模拟、图的最短路径计算等场景。在C语言中,由于没有内置的...
堆排序实现优先队列,利用优先队列做了一个小程序,有兴趣看看
数据结构优先队列,是一个简易版优先队列,输入数据及权值可以对其进行插入,删除等操作。
在广东工业大学的教程中,优先队列和二叉堆是数据结构的重要组成部分。优先队列是一种特殊的队列,其元素具有优先级属性,元素的出队顺序依赖于优先级而非入队顺序。二叉堆是一种特殊的完全二叉树,可以用来实现优先...
在讨论采用优先队列式分枝限界法求解0/1背包问题之前,我们需要先了解0/1背包问题的基本概念。0/1背包问题是一种组合优化问题,它的目标是在不超过背包总承重的前提下,从给定的一组物品中选择物品,使得选取物品的...