package Heap;
import MyInterface.Comparator;
import MyInterface.Queue;
import java.util.NoSuchElementException;
import java.util.Arrays;
public class PriorityQueue<T> implements Queue<T> {
private T[] arr;
private int qSize;
private Comparator<T> comp;
public PriorityQueue() {
comp = new Greater<T>();
qSize = 0;
arr = (T[]) new Object[10];
}
public PriorityQueue(Comparator<T> comp) {
this.comp = comp;
qSize = 0;
arr = (T[]) new Object[10];
}
public boolean isEmpty() {
return qSize == 0;
}
public T peek() {
if(qSize == 0)
throw new NoSuchElementException("empty queue");
return arr[0];
}
public T pop() {
if(qSize == 0)
throw new NoSuchElementException("empty queue");
T top = Heaps.popHeap(arr, qSize, comp);
qSize--;
return top;
}
public void push(T item) {
if(qSize == arr.length)
enlargeCapacity();
Heaps.pushHeap(arr, qSize, item, comp);
qSize++;
}
private void enlargeCapacity() {
int newCapacity = 2 * arr.length;
T[] oldArr = arr;
arr = (T[])new Object[newCapacity];
for (int i = 0; i < qSize; i++)
arr[i] = oldArr[i];
oldArr = null;
}
public int size() {
return qSize;
}
public String toString() {
T[] tmpArr = (T[]) new Object[qSize];
for (int i = 0; i < qSize; i++)
tmpArr[i] = arr[i];
Heaps.heapSort(tmpArr, comp);
return Arrays.toString(tmpArr);
}
}
Test
package Heap;
import MyInterface.*;
public class TestPriorityQueue {
public static void main(String[] args) {
PriorityQueue<Integer> pq = new PriorityQueue<Integer>(new Less<Integer>());
pq.push(new Integer(7));
pq.push(new Integer(1));
pq.push(new Integer(9));
pq.push(new Integer(0));
pq.push(new Integer(8));
pq.push(new Integer(2));
pq.push(new Integer(4));
pq.push(new Integer(3));
pq.push(new Integer(6));
pq.push(new Integer(5));
System.out.println(pq.peek()); // 9
System.out.println(pq); // [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
while(!pq.isEmpty())
System.out.print(pq.pop() + " "); // 0 1 2 3 4 5 6 7 8 9
}
}
分享到:
相关推荐
一. 优先队列的定义 优先队列是0个或多个...二. 实现本优先队列的初始化,查找,插入,删除操作,并且控制其查找,插入,删除操作的算法时间复杂度为O(logn)。采用堆正好能实现该时间复杂度。相关代码实现如下:
NULL 博文链接:https://128kj.iteye.com/blog/1665616
优先队列 优先队列(Priority Queue)是一种数据结构,它类似于常规的队列或栈,但每个元素都有与其关联的“优先级”。在优先队列中,元素的出队顺序是基于...下面是一个简单的基于数组和插入排序的优先队列实现示例:
用C语言实现一个优先队列;压缩文件中包括三个文件:1.HeapQueue.h优先队列源代码,2.main.cpp测试主函数;3.HeapQueue.h使用说明
本资源是求解最小生成树问题的,prim算法,用到了优先队列来提高效率,简化代码。
主要介绍了Python优先队列实现方法,结合实例形式分析了Python优先队列的具体定义与使用方法,具有一定参考借鉴价值,需要的朋友可以参考下
该算法基于Java语言,对算法设计中的优先队列进行了实现,本人能力有限,如有bug请多指教
对数据结构中优先队列的设计,这个仅是参考。
数据结构 基于链表实现的优先队列 Cpp文件
优先队列PriorityQueue,_堆Heap【数据结构和算法入门8】
榛子优先队列Hazelcast 通过 SPI 的优先队列实现还不成熟
利用堆实现的优先队列实质是一棵顺序存储的二叉树!所以具有很好的时间"空间性能!比传统的优先队列具有更广泛的应用前景!可在计算机的各种排队算法中推广应用
本程序主要由堆来实现优先队列的数据结构,主要有优先队列的删除,插入。算法复杂度为logn
堆排序实现优先队列,利用优先队列做了一个小程序,有兴趣看看
优先队列的实现,简单实用,实现一个按ttl时间优先的优先队列
自己实现的哈夫曼树,代码不超过100行,用到了优先队列
数据结构,课程设计优先队列实验报告 用最大堆实现的优先队列
用c写的优先队列算法,本人觉得这个还是很好用的,方便,强力推荐