数据结构-堆实现优先队列(java)

页面导航:首页 > 软件编程 > C#教程 > 数据结构-堆实现优先队列(java)

数据结构-堆实现优先队列(java)

来源: 作者: 时间:2016-01-15 14:58 【

队列的特点是先进先出。通常都把队列比喻成排队买东西,大家都很守秩序,先排队的人就先买东西。但是优先队列有所不同,它不遵循先进先出的规则,而是根据队列中元素的优先权

队列的特点是先进先出。通常都把队列比喻成排队买东西,大家都很守秩序,先排队的人就先买东西。但是优先队列有所不同,它不遵循先进先出的规则,而是根据队列中元素的优先权,优先权最大的先被取出。这就很像堆的特征:总是移除优先级最高的根节点。

重点:优先级队列,是要看优先级的,谁的优先级更高,谁就先得到权限。不分排队的顺序!

上篇文章解释了堆的概念实现,现在用堆实现优先队列:

\

 

//最大堆
import java.util.ArrayList;
public class Heap{
	private ArrayList list=new ArrayList();//用数组实现堆
	
    public Heap(){}
    public Heap(E[] objects){
    	for(int i=0;i0){
    		int parentIndex=(currentIndex-1)/2;//找到该结点的父结点
    		if(list.get(currentIndex).compareTo(list.get(parentIndex))>0){//与父节点比较
    			//如果当前结点的值大于父结点就交换位置
    			E temp=list.get(currentIndex);
    			list.set(currentIndex, list.get(parentIndex));
    			list.set(parentIndex, temp);   			
    		}
    		else
    			break;
    		currentIndex=parentIndex;
    	}    	
    }
    
    public E remove(){//删除并返回根结点,堆的特点是移除了根结点后还是堆
    	if(list.size()==0) return null;
    	
    	E removeObject=list.get(0);
    	list.set(0, list.get(list.size()-1));//把最后一个结点放在根结点的位置
    	list.remove(list.size()-1);
    	
    	int currentIndex=0;
    	while(currentIndex=list.size())break;
    		//比较左右孩子的值,使maxIndex指向值大的结点
    		 int maxIndex=leftChildIndex;
    		 if(rightChildIndexMyPriorityQueue.java

 

 

public class MyPriorityQueue {
       private Heap heap=new Heap();//用堆实现优先队列
     //入队列
       public void enqueue(E e){
       	heap.add(e); //这个add以后,堆会自己调整成一个新堆
       }
       //出队列
       public E dequeue(){
       	return heap.remove();//这移除出之后,堆会自己调整,还是一个新堆
       }
       public int getSize(){
       	return heap.getSize();
       }
      
}
TestMyPriorityQueueMainClass.java

 

 

public class TestMyPriorityQueueMainClass {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
        Patient p1=new Patient("John",2);
        Patient p2=new Patient("Tom",9);
        Patient p3=new Patient("Jack",4);
        Patient p4=new Patient("Michael",6);
        
        MyPriorityQueue priorityQueue=new MyPriorityQueue<>();
        priorityQueue.enqueue(p1);
        priorityQueue.enqueue(p2);
        priorityQueue.enqueue(p3);
        priorityQueue.enqueue(p4);
        
        while(priorityQueue.getSize()>0){
        	System.out.print(priorityQueue.dequeue()+"  ");
        }
	}
    static class Patient implements Comparable{
         private String name;
         private int priority;
         public Patient(String name,int priority){
        	 this.name=name;
        	 this.priority=priority;
         }
         public String toString(){
        	 return name+"(priority:"+priority+")";
         }
		@Override
		public int compareTo(Object oo) {//比较优先级
			// TODO Auto-generated method stub			
			return this.priority-((Patient)oo).priority;
		}
    	
    }
}

测试结果:优先级高的先输出,优先级最高的就是堆的根节点

 

\
 

 

 

 


 

Tags:

文章评论

最 近 更 新
热 点 排 行
Js与CSS工具
代码转换工具

<