java利用Heap堆實現PriorityQueue優(yōu)先隊列
本篇內容介紹了“java利用Heap堆實現PriorityQueue優(yōu)先隊列”的有關知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領大家學習一下如何處理這些情況吧！希望大家仔細閱讀，能夠學有所成！
讓客戶滿意是我們工作的目標，不斷超越客戶的期望值來自于我們對這個行業(yè)的熱愛。我們立志把好的技術通過有效、簡單的方式提供給客戶，將通過不懈努力成為客戶在信息化領域值得信任、有價值的長期合作伙伴，公司提供的服務項目有：域名與空間、網站空間、營銷軟件、網站建設、光山網站維護、網站推廣。
首先做一個優(yōu)先隊列的接口：
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是一種二叉樹，所遵守的唯一規(guī)律為：所有的子節(jié)點都要大于（小于）父節(jié)點。
增加一個節(jié)點，直接加在最后，然后用upheap排序
刪除一個節(jié)點，則把要刪除的節(jié)點與跟節(jié)點交換，然后刪除交換后的根節(jié)點（既最后一個點），然后用downheap重新排序
heap的add方法很簡單，關鍵是addall，根據是空heap或非空，，應有不同的算法以保證效率，空heap用bottom－up排序應該是最快的，至于非空的heap，則比較有挑戰(zhàn)性，以下是我自己寫的一段程序，僅供參考：
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<numbers;i++)
heap.add(elements.get(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<heap.size()){
if(c+1<heap.size() && compare(heap.get(c+1),heap.get(c))<0)
c = c + 1;
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的排序規(guī)則排列。
[@more@]
“java利用Heap堆實現PriorityQueue優(yōu)先隊列”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關的知識可以關注創(chuàng)新互聯網站，小編將為大家輸出更多高質量的實用文章！
新聞標題：java利用Heap堆實現PriorityQueue優(yōu)先隊列
當前路徑：http://muchs.cn/article42/geccec.html
成都網站建設公司_創(chuàng)新互聯，為您提供移動網站建設、品牌網站制作、網站內鏈、標簽優(yōu)化、網站營銷、定制開發(fā)
聲明：本網站發(fā)布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯
- 企業(yè)網站定制服務有哪些?求網站定做聯系方式? 2022-05-30
- 手機網站建設三個注意，否則嚴重影響轉化 2022-08-13
- 選擇制作手機版網站的原因 2016-10-31
- 手機網站建設對微信營銷有什么用？ 2013-04-20
- 教你手機商城網站運營的八大技巧 2016-12-19
- 我是做手機這塊兒的怎么樣做商城網站？ 2016-11-16
- 手機網站建設如何才能吸引用戶閱讀呢？ 2022-05-14
- 手機網站建站有哪些需要注意的事項 2013-09-27
- 手機如何做網站，手機網站建設的幾個要求 2016-11-02
- 網站建設中手機網站建設應注意幾點事項 2016-11-05
- 手機建站四大核心組成部分 2015-09-03
- 重慶手機網站建設注意項目 2021-01-17