数据结构：优先级队列 PriorityQueue

优先级队列的概念

如何实现优先级队列？

因为是通过数组存储的，它们的储存顺序都是固定的从 0 下标开始到 x，求得该节点的左子树为 2x+1，右子树为 2x+2（左子树的 +1）。如果想要由孩子节点求得其父亲节点的坐标，通过 (x-1)/2。

PriorityQueue 优先队列实现

由最后一个父亲节点开始比较，通过 size-1 的下标得到数组长度 (size-1)/2 获取到最后父亲节点的位置，然后通过父亲节点的左 2parent+1/右树 (2parent+2) 来进行比较，得到最大值在与父亲节点比较，如果大于就进行交换。每次交换完后，让其 child 继续向下移动查看孩子节点是否大于根节点。

大根堆实现

// 大根堆
public void siftDown(int parent, int usedSize) {
    int child = (2 * parent) + 1;
    while (child < usedSize) {
        // child 最大范围就是 usedSize 的长度
        if (child + 1 < usedSize && elem[child] < elem[child + 1]) {
            // 取得最大值进行比较
            child = child + 1;
        }
        if (elem[child] > elem[parent]) {
            swap(child, parent);
            // parent 往下找左右子树如果范围不满足要求，不在进行查找
            parent = child;
            child = (2 * parent) + 1;
        } else {
            // 因为只需要拿到最大值与根节点交换，如果不比 parent 大说明左右树都小，直接跳出循环
            break;
        }
    }
}

public void swap(int c, int p) {
    int tmp = elem[c];
    elem[c] = elem[p];
    elem[p] = tmp;
}

小根堆实现

步骤相同只需要更换为小于即可。