优先队列2

数组形式的优先队列和链表形式的优先队列                 

    优先队列具有排序的功能，而且可以指定它的排序方法，现在暂时先不讨论按指定的排序方式，我们就先讨论一下简单的按照值的大小来排序的情况吧。

现在我们要把100个整数放进优先队列，下面我们对比一下这两种队列的效率。

数组的比较代码：

public void add(int i){
    	int[] arr=new int[array.length+1];//每加入一个元素就要创建一个比原来数组大1长度的数组
    	int index=getIndex(0,array.length,i);
    	for(int t=0;t<index;t++){//给新数组拷贝前半部分的元素
    		arr[t]=array[t];
    	}
    	for(int s=index;s<array.length;s++){//拷贝后半部分的元素
    		arr[s+1]=array[s];
    	}
    	arr[index]=i;//在对应的位置插入元素
    	array=arr;//让原来的数组重新指向新的数组
　　}
/**
     * 通过二分法找出需要插入的元素的下标
     * @param first 数组的起始下标
     * @param end 数组的终止下标
     * @param i 要插入的元素
     * @return
     */
     private int getIndex(int first,int end,int i){
    	 int index = 0;
    	 if(first==end){//如果区间已经固定在一个下标，这就是要插入的下标
    		index=first;
    	 }else if((end-first)==1){//如果这个区间只有两个数
    		 if(i>array[first]){
    			 index=first;
    		 }else{
    			 index=end;
    		 }
    	 }else{//否则进行折半
    		 int temp=(first+end)/2;
    		if(i>array[temp]){//如果大于这个数，就在后半区间查找
    			 index=getIndex(first,temp,i);
    		}else{//否则在前半区间查找
    			 index=getIndex(temp,end,i);
    		}
    	 }
    	 return index;    	 
     }
}

 

   链表形式的代码，这要是添加元素的部分，具体的代码前面有

 

//往队列里面添加元素的方法
	public void add(int i){
		LinkNode link=root;//一个中间变量
		for(int k=0;k<size+1;k++){
			link=link.getNext();//获得下一个节点
			if(i>link.getObj()||link.getNext()==null){//如果要插入的元素大于这个节点里的元素，就插入
				LinkNode temp=new LinkNode(i);//创建一个新节点
				LinkNode back=link.getBack();//获得上一个节点
				back.setNext(temp);//上一个节点指向新节点
				temp.setBack(back);//新节点指向上一个节点
				temp.setNext(link);//新节点指向下一个节点
				link.setBack(temp);//上一个节点指向新节点
				break;//跳出循环
			}
		  }
		
		size++;
	}

 

显然用数组的形式找出要插入的位置比链表快一些，但是插入的时候数组要比链表更加麻烦，因为它要创建一个比原来长一个单位的数组，然后又得重新拷贝原来的数据。同样删除数据的时候，也需要频繁拷贝原来数组的数据。所以没有什么是绝对好的，而要看在什么情况下，有就是再有一个参照的标准下，我们才能比较出聊个东西的好和坏。

 

<!--EndFragment-->