二叉堆构造优先队列

    2. public class MaxPQ <Key extends Comparable<Key>> {
    3.     // 存储元素的数组
    4.     private Key[] pq;
    5.     // 当前 Priority Queue 中的元素个数
    6.     private int N = 0;
    8.     public MaxPQ(int cap) {
    9.         // 索引 0 不用，所以多分配一个空间
    10.         pq = (Key[]) new Comparable[cap + 1];
    11.     }
    13.     /* 返回当前队列中最大元素 */
    14.     public Key max() {
    15.         return pq[1];
    16.     }
    18.     // 父节点的索引
    19.     int parent(int root) {
    20.         return root / 2;
    21.     }
    22.     // 左孩子的索引
    23.     int left(int root) {
    24.         return root * 2;
    25.     }
    26.     // 右孩子的索引
    27.     int right(int root) {
    28.         return root * 2 + 1;
    29.     }
    31.     /* 插入元素 e */
    32.     public void insert(Key e) {
    33.         N++;
    34.         // 先把新元素加到最后
    35.         pq[N] = e;
    36.         // 然后让它上浮到正确的位置
    37.         swim(N);
    38.     }
    40.     /* 删除并返回当前队列中最大元素 */
    41.     public Key delMax() {
    42.         // 最大堆的堆顶就是最大元素
    43.         Key max = pq[1];
    44.         // 把这个最大元素换到最后，删除之
    45.         exch(1, N);
    46.         pq[N] = null;
    47.         N--;
    48.         // 让 pq[1] 下沉到正确位置
    49.         sink(1);
    50.         return max;
    51.     }
    53.     /* 上浮第 k 个元素，以维护最大堆性质 */
    54.     private void swim(int k) {
    55.         while(k>1 && less(parent(k),k)) {
    56.             exch(parent(k),k);
    57.             k = parent(k);
    58.         }
    60.     }
    62.     /* 下沉第 k 个元素，以维护最大堆性质 */
    63.     private void sink(int k) {
    64.         // 如果沉到堆底，就沉不下去了
    65.         while (left(k) <= N) {
    66.             // 先假设左边节点较大
    67.             int older = left(k);
    68.             // 如果右边节点存在，比一下大小
    69.             if (right(k) <= N && less(older, right(k)))
    70.                 older = right(k);
    71.             // 结点 k 比俩孩子都大，就不必下沉了
    72.             if (less(older, k)) break;
    73.             // 否则，不符合最大堆的结构，下沉 k 结点
    74.             exch(k, older);
    75.             k = older;
    76.         }
    77.     }
    79.     /* 交换数组的两个元素 */
    80.     private void exch(int i, int j) {
    81.         Key temp = pq[i];
    82.         pq[i] = pq[j];
    83.         pq[j] = temp;
    84.     }
    86.     /* pq[i] 是否比 pq[j] 小？ */
    87.     private boolean less(int i, int j) {
    88.         return pq[i].compareTo(pq[j]) < 0;
    89.     }
    90.     public static void main(String[] args) {
    91.         // TODO Auto-generated method stub
    93.     }
    95. }

    java库的优先队列

    • peek()//返回队首元素
    • poll()//返回队首元素，队首元素出队列
    • add()//添加元素
    • size()//返回队列元素个数
    • isEmpty()//判断队列是否为空，为空返回true,不空返回false