/**
* 优先队列的实现 * 场景:我们需要获取一组元素中的最大值或者最小值，每次取出的都是最大或者最小。使用二叉树这种数据结构 * * gao.mq * */ public class MaxPQ { private int[] pq; private int N = 0;/**
* 构造一个空的二叉树，物理上存储是一个数组，逻辑上理解成一个二叉树。 * * maxN */ public MaxPQ(int maxN) { pq = new int[maxN]; }public boolean isEmpty() {
return N == 0; }public int size() {
return N; }/**
* 插入一个元素 * 在插入一个元素的时候，插入的这个值可能是数组中最大的值。所以要进行一步比较操作。 * * value */ public void insert(int value) { pq[++N] = value; swim(N); }/**
* 数组插入元素时的上浮操作 * 当前元素的索引假设是i,它的父节点则为i/2,它的子结点则为2*i和2*i+1 * * 这个操作很简单，我们只要保证索引i的值不小于索引1的时候就比较当前结点和它的父节点 * * key */ private void swim(int key) { while (key > 1 && pq[key] > pq[key / 2]) { int temp = pq[key]; pq[key] = pq[key / 2]; pq[key / 2] = temp; key = key / 2; } }/**
* 删除最大元素 * 我们把最大值上浮到索引1了，所以删除只需要把数组pa[1]取出即可。 * 这时要把第二大的元素放到第一个位置,我们把pq[N]也就是最后一个元素放入到第一个位置 * * */ public int delMax() { int max = pq[1]; pq[1] = pq[N--]; pq[N + 1] = 0; sink(1); return max; }/**
* 下沉操作 * 找到当前结点的两个子结点，找到大的和当前结点比较。然后交换 * 一直下浮到合适的位置 * * @param k */ private void sink(int k) { while (2 * k <= N) { int j = 2 * k; if (j < N && less(j, j + 1)) { j++; } if (!less(k, j)) break; int temp = pq[k]; pq[k] = pq[j]; pq[j] = temp; k = j; } }/**
* 比较兄弟结点之间的大小 * * @param j * @param i * @return */ private boolean less(int j, int i) { if (pq[j] > pq[i]) { return false; } return true; }public void travse() {
for (int i = 1; i < pq.length; i++) { System.out.println(pq[i]); } }public static void main(String[] args) {
MaxPQ pq = new MaxPQ(10); pq.insert(5); pq.insert(2); pq.insert(3); pq.insert(10); pq.insert(7); pq.delMax(); pq.travse(); }