希望最小優先級隊列支持decrease操作，即減少某個數據的值背景偶堆(paringheap)231264108127119211715192513偶堆是滿足堆條件的m叉樹，即將二叉樹擴展成m叉樹。偶堆12671192382542112131017151955插入操作：1、生成只有根結點的偶堆2、合并偶堆31923126410812711921152513231264108127119211715192513減少操作：1、移除子樹2、合并偶堆12671192382542112131015319偶堆23264108127119211715192513231264108127119211715192513刪除操作1、移除根結點2、從左至右兩兩合并3、從右至左逐一合并偶堆26711923825421121310171519偶堆26711942110171519238251213偶堆26711942110171519238251213偶堆偶堆在實現時可以采用孩子-兄弟表示法偶堆的刪除操作的時間復雜度O(n)，其它操作都是O(1)一系列操作的均攤時間復雜度可能是O(logn)基于堆的支持decrease操作的優先級隊列public

classPriorityQueueWithDecrease<T>{

privateObject[]elements;

private

int

size;

//Entry封裝了數據T，增加了在堆的位置

public

static

classEntry<T>{

private

int

index;//堆中的位置

publicTdata;//數據，需要能比較大小

publicEntry(Tvalue){

this.data=value; }

publicStringtoString(){

return

index+":"+data; } }

publicPriorityQueueWithDecrease(int

maxSize){

elements=newObject[maxSize]; }引入Entry封裝：數據位置基于堆的支持decresae操作的優先級隊列

public

booleanoffer(Entry<T>e){

if(e==null)

throw

newNullPointerException();

int

i=size;

if(i>=elements.length)

throw

newIllegalStateException(String.valueOf(i));

size=i+1;

if(i==0)

elements[0]=e;

else{ siftUp(i,e); }

return

true; }更改了offer的參數類型基于堆的支持decresae操作的優先級隊列

private

voidsiftUp(int

k,Entry<T>x){ Comparable<?superT>key=(Comparable<?superT>)x.data;

while(k>0){

int

parent=(k-1)>>>1; Entry<T>e=(Entry<T>)elements[parent];

if(key.compareTo(e.data)>0)

break;

elements[k]=e;

e.index=k;//設置數據的位置

k=parent; }

elements[k]=x;

x.index=k;//設置數據在堆中的位置 }更改了siftUp、siftDown向Entry對象反饋位置基于堆的支持decresae操作的優先級隊列

private

voidsiftUp(int

k,Entry<T>x){ Comparable<?superT>key=(Comparable<?superT>)x.data;

while(k>0){

int

parent=(k-1)>>>1; Entry<T>e=(Entry<T>)elements[parent];

if(key.compareTo(e.data)>0)

break;

elements[k]=e;

e.index=k;//設置數據的位置

k=parent; }

elements[k]=x;

x.index=k;//設置數據在堆中的位置 }更改了siftUp、siftDown向Entry對象反饋位置基于堆的支持decresae操作的優先級隊列

public

voiddecrease(Entry<T>e){ siftUp(e.index,e); }decrease:O(logn)基于堆的支持decresae操作的優先級隊列

public

static

voidmain(String[]args){ Integer[]distance={7,1,9,2,8,6,5,4,10}; PriorityQueueWithDecrease<Integer>queue=

newPriorityQueueWithDecrease<>(distance.length); Entry<Integer>[]data=(Entry<Integer>[])newEntry<?>[distance.length];

for(int

i=0;i<data.length;i++)

data[i]=newEntry<>(distance[i]);

for(int

i=0;i<distance.length;i++){

queue.offer(data[i]); } System.out.println(queue);基于堆的支持decresae操作的優先級隊列

data[8].data=3;

queue.decrease(data[8]); System.out.println(queue);

while(queue.size()!=0){ Integerp=queue.poll(); System.out.print(p+""); } System.out.println(); }0:11:22:53:44:85:96:67:78:100:11:22:53:34:85:96:67:78:4123456789堆包裝數據intindex2Tdataintindex1Tdataintindex0Tdata缺點data優先級隊列的使用者增加了困難：記住隊列有哪些數據改變了offer的參數類型，不符合IQueue接口不改變offer的參數類型，符合IQueue接口基于堆的支持decresae操作的優先級隊列public

classPriorityQueueWithDecrease2<T>implementsIQueue<T>{

privateObject[]elements;

private

int

size;

privateMap<T,Entry<T>>dic=newHashMap<>();堆的數據類型是Entry<T>，offer和decrease的參數類型是T使用Map將T映射到Entry<T>不改變offer的參數類型，符合IQueue接口基于堆的支持decresae操作的優先級隊列

public

booleanoffer(Te){

if(e==null)

throw

newNullPointerException();

int

i=size;

if(i>=elements.length)

throw

newIllegalStateException(String.valueOf(i));

size=i+1; Entry<T>entry=newEntry<>(e);

entry.index=0;

dic.put(e,entry);//加入map

if(i==0)

elements[0]=entry;

else{ siftUp(i,entry); }

return

true; }基于堆的支持decresae操作的優先級隊列

private

voidsiftUp(int

k,Entry<T>x){ Comparable<?superT>key=(Comparable<?superT>)x.data;

while(k>0){

int

parent=(k-1)>>>1; Entry<T>e=(Entry<T>)elements[parent];

if(key.compareTo(e.data)>0)

break;

elements[k]=e;

e.index=k;//設置數據的位置

k=parent; }

elements[k]=x;

x.index=k;//設置數據在堆中的位置 }基于堆的支持decresae操作的優先級隊列//修改前后是同一個對象T，并且equals遵從同一個對象相等的原則

public

voiddecrease(Tvalue){ Entry<T>e=dic.get(value); siftUp(e.index,e); }1個參數：更改了值的對象基于堆的支持decresae操作的優先級隊列//修改前后是兩個不同的對象

public

voiddecrease(ToldValue,TnewValue){ Entry<T>e=dic.get(oldValue);

e.data=newValue; siftUp(e.index,e); }2個參數：舊值對象，新值對象1個參數：更改值的對象，值更改了后，可能euqals不認為相等了基于堆的支持decresae操作的優先級隊列

public

static

voidmain(String[]args){ Integer[]distance={7,1,9,2,8,6,5,4,10}; PriorityQueueWithDecrease2<Integer>queue=new

PriorityQueueWithDecrease2<>(distance.length);

for(int

i=0;i<distance.length;i++){

queue.offer(distance[i]); } System.out.println(queue); Integere=Integer.valueOf(5);

queue.decrease(distance[8],e);

distance[8]=e; System.out.println(queue); }0:11:22:53:44:85:96:67:78:100:11:22:53:44:85:96:67:78:5基于堆的支持decresae操作的優先級隊列 System.out.println("---------------------------");

e=Integer.valueOf(3);

queue.decrease(distance[8],e);

distance[8]=e; System.out.println(queue);

while(queue.size()!=0){ Integerp=queue.poll(); System.out.print(p+""); } System.out.println();---------------------------0:11:22:33:44:85:96:67:78:5123456789基于堆的支持decresae操作的優先級隊列

classTestimplementsComparable<Test>{ Integerd; Test(int

i){

d=i; }

public

intcompareTo(Testother){

returnIpare(this.d,other.d); }

publicStringtoString(){

return

d+""; } } PriorityQueueWithDecrease2<Test>queue1=newPriorityQueueWithDecrease2<>(10);

queue1.offer(newTest(10));

queue1.offer(newTest(8));

queue1.offer(newTest(12)); Testt=newTest