基于堆的优先队列

package com.snail.basic;

public class MaxPQ<Key extends Comparable<Key>> {
    private Key[] pq;
    private int N;
    public MaxPQ(int Max){
        pq = (Key[])new Comparable[Max];
    }
    // 判断是否为空
    public boolean isEmpty(){
        return N==0;
    }
    // 返回队列大小
    public int size(){
        return N;
    }
    // 插入
    public void insert(Key v){
        pq[++N]=v;
        swim(N);
    }
    // 删除最大元素
    public Key delMax(){
        Key max = pq[1];
        exch(1,N--);
        pq[N+1]=null;
        sink(1);
        return max;
    }
    // 比较
    public boolean less(int i, int j){
        return pq[i].compareTo(pq[j])>0;
    }
    // 交换
    public void exch(int i, int j){
        Key temp = pq[i];
        pq[i] = pq[j];
        pq[j] = temp;
    }
    // 由下向上交换
    public void swim(int k){
        while (k>1 && less(k,k/2)){
            exch(k,k/2);
            k = k/2;
        }
    }
    // 由上向下交换
    public 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;
            exch(k,j);
            k = j;
        }
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券