java利用Heap堆实现PriorityQueue优先队列
本篇内容介绍了“java利用Heap堆实现PriorityQueue优先队列”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！
让客户满意是我们工作的目标，不断超越客户的期望值来自于我们对这个行业的热爱。我们立志把好的技术通过有效、简单的方式提供给客户，将通过不懈努力成为客户在信息化领域值得信任、有价值的长期合作伙伴，公司提供的服务项目有：域名与空间、网站空间、营销软件、网站建设、光山网站维护、网站推广。
首先做一个优先队列的接口：
import java.util.List;
public interface PriorityQueue {
void add(Object o);
void addAll(List elements);
Object remove();
boolean isEmpty();
int size();
}
接下来，用java写一个heap结构，实现priority queue接口：
heap是一种二叉树，所遵守的唯一规律为：所有的子节点都要大于（小于）父节点。
增加一个节点，直接加在最后，然后用upheap排序
删除一个节点，则把要删除的节点与跟节点交换，然后删除交换后的根节点（既最后一个点），然后用downheap重新排序
heap的add方法很简单，关键是addall，根据是空heap或非空，，应有不同的算法以保证效率，空heap用bottom－up排序应该是最快的，至于非空的heap，则比较有挑战性，以下是我自己写的一段程序，仅供参考：
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Arrays;
public class Heap implements PriorityQueue {
protected Comparator comparator;
final static int ROOT_INDEX = 0;
final static int PRE_ROOT_INDEX = ROOT_INDEX - 1;
List heap;
public Heap() {
heap = new ArrayList();
}
public Heap(Comparator c) {
heap = new ArrayList();
comparator = c;
}
/* (non-Javadoc)
* @see PriorityQueue#add(java.lang.Object)
*/
public void add(Object o) {
heap.add(o);
int index = heap.size() - 1;
while (index > ROOT_INDEX) {
index = stepUpHeap(index);
}
}
/**
* Enforce ordering for heap element and its parent.
* Indices start from ROOT_INDEX (inclusive).
* @param index valid non-root heap position
* @return index of parent in heap, if swap occurs, otherwise ROOT_INDEX
*/
protected int stepUpHeap(int index) {
int parentIndex = parent(index);
Object element = heap.get(index);
Object parent = heap.get(parentIndex);
if (compare(parent, element) > 0) { // heap is out of order here
heap.set(parentIndex, element);
heap.set(index, parent);
return parentIndex; // jump to parent of index
} else // heap is OK
return ROOT_INDEX; // so jump to root
}
/**
* Compare elements using comparator if it exists.
* Otherwise assume elements are Comparable
* @param element
* @param other
* @return result of comparing element with other
*/
protected int compare(Object element, Object other) {
if (comparator == null) {
Comparable e = (Comparable) element;
Comparable o = (Comparable) other;
return e.compareTo(o);
} else
return comparator.compare(element, other);
}
/**
* Index of parent in heap.
* @param index to find parent of
* @return index of parent
*/
protected int parent(int index) {
return (index - PRE_ROOT_INDEX) / 2 + PRE_ROOT_INDEX;
}
public String toString() {
return heap.toString();
}
/* (non-Javadoc)
* @see PriorityQueue#isEmpty()
*/
public boolean isEmpty() {
return heap.isEmpty();
}
/* (non-Javadoc)
* @see PriorityQueue#size()
*/
public int size() {
return heap.size();
}
/* (non-Javadoc)
* @see PriorityQueue#remove()
*/
public Object remove() throws RuntimeException{
if (isEmpty())
throw new RuntimeException();
int index = heap.size() - 1;
Object least;
if(index==0){
least = heap.get(index);
heap.remove(index);
}
else{
Object element = heap.get(index);
least = heap.get(ROOT_INDEX);
heap.set(ROOT_INDEX, element);
heap.set(index, least);
heap.remove(index);
stepDownHeap(ROOT_INDEX);
}
return least;
}
/* (non-Javadoc)
* @see PriorityQueue#addAll(java.util.List)
*/
public void addAll(List elements) {
int numbers = elements.size();
for(int i=0;i
int n=1,rows=0;
for(rows=0;n<= heap.size();rows++){
n = n*2;
}
for(int i=rows-1;i>=1;i--){
for(int j=(int)(Math.pow(2,i-1)-1);j<=(int)(Math.pow(2,i)-2);j++){
stepDownHeap(j);
}
}
}
public static void sort(Comparable[] data) {
Heap cpr = new Heap();
List middle = Arrays.asList(data);
cpr.addAll(middle);
for(int i=data.length-1;i>=0;i--)
data[i] = (Comparable)(cpr.remove());
}
public static void sort(Object[] data, Comparator c) {
Heap cpr = new Heap(c);
List middle = Arrays.asList(data);
cpr.addAll(middle);
for(int i=data.length-1;i>=0;i--)
data[i] = cpr.remove();
}
public void stepDownHeap(int index){
int p = index;
int c = 2*p + 1;
Object temp = heap.get(p);
while(c
if(compare(temp,heap.get(c))<=0)
break;
else {
heap.set(p,heap.get(c));
p = c;
c = 2*p + 1;
}
}
heap.set(p,temp);
}
}
最后是一段测试程序：
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Random;
public class PQTest {
///////////////////////////////////////////////////////
//
// static declarations
//
///////////////////////////////////////////////////////
public static void main(String[] args) {
PQTest test = new PQTest();
test.constructor();
test.add();
test.remove();
test.addAll();
test.sort();
}
static int nextIndex;
final static long SEED = 88888L;
final static Random random = new Random(SEED);
static Integer[] arrayData; // backing store for data
static List data;
static void makeData(int n) {
random.setSeed(SEED);
arrayData = new Integer[n];
for (int i = 0; i < n; ++i) {
arrayData[i] = (new Integer(i));
}
data = Arrays.asList(arrayData);
Collections.shuffle(data, random);
}
static void testAssert(boolean b, String s) {
if (!b) throw new RuntimeException(s);
}
static Comparator comparableComparator() {
return new Comparator() {
public int compare(Object x, Object y) {
return ((Comparable) x).compareTo(y);
}
};
}
static Comparator reverseComparator(Comparator c) {
return new ReverseComparator(c);
}
static class ReverseComparator implements Comparator {
Comparator c;
ReverseComparator(Comparator c) {
this.c = c;
}
public int compare(Object x, Object y) {
return - c.compare(x,y);
}
}
static CountComparator countComparator(Comparator c) {
return new CountComparator(c);
}
static class CountComparator implements Comparator {
Comparator c;
CountComparator(Comparator c) {
this.c = c;
}
int count = 0;
public int getCount() {
return count;
}
public void clearCount() {
count = 0;
}
public int compare(Object x, Object y) {
++count;
return c.compare(x,y);
}
}
///////////////////////////////////////////////////////
//
// instance specific declarations
//
///////////////////////////////////////////////////////
// instance variable
PriorityQueue pq; // priority queue to be tested
Comparator c;
// instance methods for testing priority queue operation
void constructor() {
System.out.println("new Heap()");
pq = new Heap();
checkPQ(true, 0);
System.out.println();
}
void add() {
makeData(16);
for (int i = 0; i < 16; ++i) {
Object o = data.get(i);
System.out.println("add(" + o + ") ...");
pq.add(o);
checkPQ(false, i+1);
}
System.out.println();
}
void remove() {
for (int i = pq.size(); i > 0; --i) {
checkPQ(false, i);
System.out.print("remove() = ");
Object o = pq.remove();
System.out.println(o);
}
checkPQ(true, 0);
System.out.println();
}
void addAll() {
c = countComparator(comparableComparator());
pq = new Heap(c);
makeData(99);
addN(0,16);
addN(16,16);
addN(16,17);
addN(17,19);
addN(19,27);
addN(27,43);
addN(43,48);
addN(48,99);
System.out.println();
}
void addN(int from, int to) {
int size = pq.size();
List dataN = data.subList(from,to);
int n = to - from;
System.out.println("addAll(" + dataN + ") ... " + n + " items ...");
pq.addAll(dataN);
checkPQ(false, size+n);
System.out.println("Comparison count = " + ((CountComparator) c).getCount());
((CountComparator) c).clearCount();
}
void sort() {
Comparator c = null;
System.out.println("Testing sort() with natural ordering");
sortWithComparator(c);
System.out.println();
System.out.println("Testing sort() with reverse natural ordering");
c = reverseComparator(comparableComparator());
sortWithComparator(c);
System.out.println();
System.out.println("Testing sort() with natural ordering and comparison count");
c = countComparator(comparableComparator());
sortWithComparator(c);
System.out.println("Comparison count = " + ((CountComparator) c).getCount());
System.out.println();
System.out.println("Testing sort() with reverse natural ordering and comparison count");
c = countComparator(reverseComparator(comparableComparator()));
sortWithComparator(c);
System.out.println("Comparison count = " + ((CountComparator) c).getCount());
System.out.println();
}
void sortWithComparator(Comparator c) {
makeData(64);
System.out.println("Unsorted: " + data);
Heap.sort(arrayData, c);
System.out.println("Sorted: " + data);
System.out.println();
}
// helper methods
void checkPQ(boolean isEmpty, int size) {
System.out.println("PriorityQueue: " + pq);
testAssert(pq.isEmpty() == isEmpty, "isEmpty()");
testAssert(pq.size() == size, "size()");
}
}
对于非空的heap，应该有更快的算法（但是效率都是o（nlogn）），只是结果可能会有所不同，但是仍然是按照heap的排序规则排列。
[@more@]
“java利用Heap堆实现PriorityQueue优先队列”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注创新互联网站，小编将为大家输出更多高质量的实用文章！
本文标题：java利用Heap堆实现PriorityQueue优先队列
标题URL：http://ybzwz.com/article/geccec.html
