import java.util.Arrays;

public class MyHeap {

    public int[] elem;
    public int usedSized;

    public MyHeap() {
        this.elem = new int[10];
    }

    public void initArray(int[] arr) { //初始化堆
        for (int i = 0; i < arr.length; i++) {
            this.elem[i] = arr[i];
            this.usedSized++;
        }
    }

    public void createHeap() {
        for (int parent = (usedSized-1-1); parent >= 0; parent--) {
            siftDown(parent, usedSized);
        }
    }

    private void siftDown(int parent, int usedSized) { // 向下调整
        int child = parent * 2 + 1;
        while (child < usedSized) {
            if (child + 1 < usedSized && elem[child] < elem[child+1]) {
                child++;
            }
            if (elem[child] > elem[parent]) {
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
                parent = child;
                child = 2 * parent + 1;
            } else {
                break;
            }
        }
    }

    public void offer(int val) {
        if (isFull()) {
            this.elem = Arrays.copyOf(elem, 2*elem.length);
        }
        elem[usedSized] = val;
        siftUp(usedSized);
        usedSized++;
    }

    private void siftUp(int child) { // 向上调整
        int parent = (child - 1) / 2;
        while (parent >= 0) {
            if (elem[child] > elem[parent]) {
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
                child = parent;
                parent = (child - 1) / 2;
            } else {
                break;
            }
        }
    }

    public boolean isFull() {
        return usedSized == this.elem.length;
    }

    public int poll() { // 堆的删除
        if (isEmpty()) {
            return -1;
        }
        int val = elem[0];
        swap(0, usedSized - 1);
        usedSized--;
        siftDown(0, usedSized);
        return val;
    }

    private void swap(int a, int b) {
        int tmp = elem[a];
        elem[a] = elem[b];
        elem[b] = tmp;
    }

    public boolean isEmpty() { // 获取堆顶元素
        return usedSized == 0;
    }

    public int peek() {
        if (isEmpty()) {
            return -1;
        }
        return elem[0];
    }

    public void heapSort() { // 堆排序
        int end = usedSized - 1;
        while (end > 0) {
            swap(0, end);
            siftDown(0, end);
            end--;
        }
    }
}

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

public class Test {
    public static void main(String[] args) {
        // 无参构造，默认是小堆
        PriorityQueue<Integer> queue1 = new PriorityQueue<>();
        // 创建容量为100的优先级队列
        PriorityQueue<Integer> queue2 = new PriorityQueue<>(100);

        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        // 用其他集合创捷
        PriorityQueue<Integer> queue3 = new PriorityQueue<>(list);
    }
}

import java.util.Comparator;
import java.util.PriorityQueue;

public class Test implements Comparator<Integer> { // 实现Comparator接口
    public static void main(String[] args) {
        PriorityQueue<Integer> queue1 = new PriorityQueue<>(new Test());
        queue1.offer(1);
        queue1.offer(2);
        queue1.offer(3);
        queue1.offer(4);
        queue1.offer(5);
        System.out.println(queue1);
    }

    @Override // 重写 compare 方法
    public int compare(Integer o1, Integer o2) {
        return o2 - o1;
    }

    @Override
    public boolean equals(Object obj) {
        return false;
    }
}

import java.util.PriorityQueue;

public class Test {
    public static void main(String[] args) {
        PriorityQueue<Integer> queue1 = new PriorityQueue<>();
        queue1.offer(1); // 插入元素
        queue1.offer(2);
        queue1.offer(3);
        System.out.println(queue1.peek()); // 获取堆顶元素
        queue1.poll(); // 删除堆顶元素
        System.out.println(queue1.size()); // 返回堆大小
        queue1.clear(); // 清空堆
        System.out.println(queue1.isEmpty()); // 返回堆是否为空
    }
}