优先队列算法实现(Java)

import java.util.HashMap; import java.util.Vector; public class Heap { private Vector<Object> heap; private HashMap<Object,Object> key; public Heap(Vector<Object> heap,Vector<Object> key){ this.heap=new Vector<Object>(heap); this.key=new HashMap<Object,Object>(); for(Integer i=0;i<heap.size();i++){ this.key.put(heap.get(i), key.get(i)); } this.creatHeap(); } public Boolean heapUp(Integer location){ Integer parent; if(location>=1){ parent=(location-1)/2; if((Integer)key.get(heap.get(location))<(Integer)key.get(heap.get(parent))){ Integer temp=(Integer)heap.get(location); heap.set(location, heap.get(parent)); heap.set(parent, temp); this.heapUp(parent); } else{ return true; } } return true; } public Boolean heapDown(Integer location){ Integer left,right,length,child=0; length=heap.size(); if(2*(location+1)>length){ return true; } else if(2*(location+1)<length){ left=2*(location+1)-1; right=left+1; if(Math.min((Integer)key.get(heap.get(left)),(Integer)key.get(heap.get(right)))==(Integer)key.get(heap.get(left))){ child=left; }else{ child=right; } } else if(2*(location+1)==length){ child=length-1; } if((Integer)key.get(heap.get(child))<(Integer)key.get(heap.get(location))){ Integer temp1=(Integer)heap.get(location); heap.set(location, heap.get(child)); heap.set(child, temp1); this.heapDown(child); } return true; } public void creatHeap(){ for(Integer i=0;i<heap.size();i++){ this.heapUp(i); } } public String toString(){ return "所有元素:"+heap; } public void changeKey(Object v,Object k){ //把节点V的key改为k Integer mark=0; if((Integer)this.key.get(v)>(Integer)k){ mark=1; } this.key.put(v, k); if(mark==0){ this.heapDown(this.heap.indexOf(v)); } else{ this.heapUp(this.heap.indexOf(v)); } } public Object extracctMin(){ Object temp=heap.get(0); heap.set(0, heap.get(heap.size()-1)); heap.remove(heap.size()-1); key.remove(temp); this.heapDown(0); return temp; } }