java-优先队列

package Heap;

import java.util.Arrays;

//优先队列
public class MyPriorityQueue {
    //array看起来是一个数组，其实应该是一个堆的结构
    private int[] array = new int[100];
    private int size = 0;
//入队列
    public void offer(int x) {
        array[size] = x;
        size++;
        //把新元素进行向上调整
        shiftUp(array,size-1);
    }
    //size这个参数没用上，因为判定调整完了，只需要和0号位置比较即可，不需要知道堆有多大
    private static void shiftUp(int[] array,int index) {
        int child = index;
        int parent = (child - 1)/2;
        while(child > 0) {
            if (array[parent] < array[child]) {
                //父节点小于子节点，当前不符合大堆要求
                int tmp = array[parent];
                array[parent] = array[child];
                array[child] = tmp;
            }else {
                break;
            }
            child = parent;
            parent = (child - 1) /2;
        }
    }

    //出队列
    //删除堆顶元素，直接把数组中的最后一个元素给赋值到堆顶元素上，同时size--
    //接下来从根节点出发进行向下调整即可
    public int poll() {
        //下标为0的元素就是队首元素，删掉的同时，我们也希望剩下的结构仍然是一个堆
        int oldValue = array[0];
        array[0] = array[size - 1];
        size--;
        shiftDown(array,size,0);
        return oldValue;
    }

    private static void shiftDown(int[] array,int size,int index){
        int parent = index;
        int child = 2 * parent +1;//按照parent下标找到左子树下标
        while(child < size) {
            //比较左右子树，找到最大值
            if (child + 1 < size && array[child + 1] > array[child]){
                child = child+1;
            }
            //上述比较完已经不知道child是左子树还是右子树
            //但知道的是child下标一定对应左右子树最小值的下标

            //拿child位置的元素和parent位置的元素比较
            if (array[child] > array[parent]) {
                //不符合小堆的规则，就交换父子节点
                int tmp = array[child];
                array[child] = array[parent];
                array[parent] = tmp;
            }else {
                //调整完毕，不需要继续了
                break;
            }
            //更新parent和child，循环处理下一层的数据
            parent = child;
            child = 2 * parent +1;
        }
    }

    public int peek() {
        return array[0];
    }

    public boolean isEmpty() {
        return size == 0;
    }
    public static void main(String[] args) {
        MyPriorityQueue queue = new MyPriorityQueue();
        queue.offer(9);
        queue.offer(5);
        queue.offer(2);
        queue.offer(7);
        queue.offer(3);
        queue.offer(6);
        queue.offer(8);



        while(!queue.isEmpty()) {
              int cur = queue.poll();
              System.out.print(cur + " ");
          }
    }
}

public class TestPriorityQueue {
    public static void main(String[] args) {
        PriorityQueue queue = new PriorityQueue<>();
        queue.offer(9);
        queue.offer(5);
        queue.offer(2);
        queue.offer(7);
        queue.offer(1);
while(!queue.isEmpty()) {
    int cur = queue.poll();
    System.out.print(cur + " ");
}
    }
}