우선 순위 대기 열 (더미) 의 원리 및 구현

많은 응용 에서 우 리 는 우선 순위 상황 에 따라 처리 대상 을 처리 해 야 한다. 예 를 들 어 우선 순위 가 가장 높 은 대상 을 처리 한 다음 에 높 은 대상 을 처리 해 야 한다.가장 쉬 운 예 는 휴대 전화 에서 게임 을 할 때 전화 가 오 면 시스템 이 들 어 오 는 전 화 를 우선 처리 해 야 한 다 는 것 이다.이런 상황 에서 우리 의 데이터 구 조 는 두 가지 가장 기본 적 인 조작 을 제공 해 야 한다. 하 나 는 최고 우선 순위 대상 으로 돌아 가 는 것 이 고 하 나 는 새로운 대상 을 추가 하 는 것 이다.이 데이터 구 조 는 우선 순위 대기 열 (Priority Queue) 입 니 다.

public class PriorityQueue {
    private int capacity=10;//    
    private int[] array=new int[capacity];//         
    private int size=0;//          


    //    。       ，             ，        
    private static  void shiftDown(int[] array,int size,int index){
        int left=2*index+1;
        while (left=0;i--){
            shiftDown(array,size,i);
        }
    }


    //    ，       ，index      ，parent     ，    ，     
    private static void shiftUp(int[] array,int index){
        while (index>0){
            int parent=(index-1)/2;
            if(array[parent]>=array[index]){
                break;
            }
            int flag=array[parent];
            array[parent]=array[index];
            array[index]=flag;
            index=parent;
        }
    }
    
    //        ，    
    private void grow(int minCapacity){
        if(minCapacity<0){
            throw new OutOfMemoryError();
        }
        int oldCapacity=array.length;
        int newCapacity=oldCapacity+oldCapacity/2;
        array=Arrays.copyOf(array,newCapacity);
    }
    
    //         ，      
    public boolean offer(int e){
        int i=size;
        if(i>=array.length){
            grow(capacity);
        }
        if(i==0){
            array[0]=e;
            size=i+1;
        }else {
        array[size++]=e;
        shiftUp(array,size-1);
        }
        return true;
    }
    
    //       ，    ，         
    public int poll(){
        int oldValue=array[0];
        array[0]=array[--size];
        shiftDown(array,size,0);
        return oldValue;
    }
    public int peek(){
        return array[0];
    }
    public String toString(){
        return  Arrays.toString(Arrays.copyOf(array,size));
    }
    public static void main(String[] args) {
        PriorityQueue queue=new PriorityQueue();
        for(int i=0;i<12;i++){
            queue.offer(i);
        }
        System.out.println(queue);
    }
}

효 과 를 시험 해 보 겠 습 니 다.

[11, 9, 10, 6, 8, 5, 4, 0, 3, 2, 7, 1]

Process finished with exit code 0