java实现优先对列的入队出队取队首元素

╰半夏微凉° 2023-06-13 04:43 19阅读 0赞

public class PriorityQueue {
        
        private int[] array = new int[100];  //数组时队列本体
        private int size = 0;
    
        //入队
        public void offer (int x) {
        
            if(size >= array.length) {
        
                return;
            }
            array[size] = x;
            size++;
            shiftUp(array,size - 1);
        }
          //上浮调整
        private void shiftUp(int[] array,int index) {
        
            int child = index;
            int parent = (index - 1) / 2;
            while (child > 0) {
        
                if(array[parent] < array[child]) {
        
                    swap(array,parent,child);
                } else {
        
                    break;
                }
                child = parent;
                parent = (child -1) / 2;
            }
        }
    
        //下沉调整
        private void shiftDown(int[] array,int size,int index) {
        
            int parent = index;
            int child = 2 * parent + 1;
            while (child < size) {
        
                if(child + 1 <size && array[child + 1] >array[child]) {
        
                    child = child + 1;
                }
                if(array[child] > array[parent]) {
        
                    swap(array,parent,child);
                } else {
        
                    break;
                }
                parent = child;
                child = 2 * parent + 1;
            }
        }
    
        //交换
        public static void swap (int[] array,int x,int y) {
        
            int tmp = array[x];
            array[x] = array[y];
            array[y] = tmp;
        }
    
        public Integer poll() {
        
            if(size == 0) {
        
                return null;
            }
            int ret = array[0];
            array[0] = array[size - 1];
            size--;
            shiftDown(array,size,0);
            return ret;
        }
    }