优先级队列的发明主要是用于删除最大数（最小数）
首先定义一个数组用于实现优先级队列，然后定义一个指针N来控制数组里的最后一个元素。
int[] key; int N;
然后定义构造函数并给数组初始化长度。
Pq(int capacity) {
key = new int[capacity];
}
然后判空操作。
public boolean isEmpty() {
return N == 0;
}
public void exchange(int i,int j) {
int temp = key[i];
key[i] = key[j];
key[j] = temp;
}
public boolean more(int v,int w) {
return v > w;
}
接下来就是最重要的插入元素操作和删除最大元素操作了。
思路1： 无序插入O(1)，删除最大O(N)
插入
public void insert(int x) {
key[N++] = x;
}
public int deleteMax() {
if (isEmpty())
return 0;
int maxIndex = 0;
for (int i = 1; i < N; i++) {
if (more(key[i],key[maxIndex]))
maxIndex = i;
}
exchange(N - 1,maxIndex);
return key[--N];
}
思路2：有序插入O(N)，删除最大O(1)
尽管可以采取二分查找的思路来寻找插入的位置，但是由于插入元素后，插入元素的后面所有元素都需要向后移动一位，因此时间复杂度依然为O(N)。
插入
public void insert(int x) {
if (isEmpty()) {
key[N++] = x;
return;
}
int left = 0;
int right = N - 1;
while (left <= right) {
int middle = (left + right) / 2;
if (key[middle] == x) {
put(middle,x);
return;
}
if (more(key[middle],x))
right = middle - 1;
else
left = middle + 1;
}
put(left,x);
}
public void put(int middle,int x) {
for (int i = N - 1; i >= middle; i--)
key[i + 1] = key[i];
key[middle] = x;
N++;
}
删除
public int deleteMax() {
if (isEmpty())
return 0;
return key[--N];
}
