Java-堆与优先队列

堆（Heap）

基础表示

二叉堆是一颗完全二叉树
什么是完全二叉树？
- 将数据一层一层的排列成树的形状，按照树从左到右的顺序，直到放不下为止
- 也就是说可以如果有空缺的元素，必须是在树的右下方

性质

最大堆：堆中某个节点的值总是不大于其父节点的值（相应也有最小堆）
节点的大小与层次无关

动态数组表示最大堆

public class MaxHeap<E extends Comparable<E>> {

    private Array<E> data;

    public MaxHeap(int capacity){
        data = new Array<>(capacity);
    }

    public MaxHeap(){
        data = new Array<>();
    }

    public MaxHeap(E[] arr){
        data = new Array<>(arr);
        for(int i = parent(arr.length - 1) ; i >= 0 ; i --)
            siftDown(i);
    }

    // 返回堆中的元素个数
    public int size(){
        return data.getSize();
    }

    // 返回一个布尔值, 表示堆中是否为空
    public boolean isEmpty(){
        return data.isEmpty();
    }

    // 返回完全二叉树的数组表示中，一个索引所表示的元素的父亲节点的索引
    private int parent(int index){
        if(index == 0)
            throw new IllegalArgumentException("index-0 doesn't have parent.");
        return (index - 1) / 2;
    }

    // 返回完全二叉树的数组表示中，一个索引所表示的元素的左孩子节点的索引
    private int leftChild(int index){
        return index * 2 + 1;
    }

    // 返回完全二叉树的数组表示中，一个索引所表示的元素的右孩子节点的索引
    private int rightChild(int index){
        return index * 2 + 2;
    }

添加元素和Sift up

// 向堆中添加元素
public void add(E e){
    data.addLast(e);
    siftUp(data.getSize() - 1);
}

private void siftUp(int k){

    while(k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0 ){
        data.swap(k, parent(k));
        k = parent(k);
    }
}

取出元素和Sift down

// 看堆中的最大元素
public E findMax(){
    if(data.getSize() == 0)
        throw new IllegalArgumentException("Can not findMax when heap is empty.");
    return data.get(0);
}

// 取出堆中最大元素
public E extractMax(){

    E ret = findMax();

    data.swap(0, data.getSize() - 1);
    data.removeLast();
    siftDown(0);

    return ret;
}

private void siftDown(int k){

    while(leftChild(k) < data.getSize()){
        int j = leftChild(k); // 在此轮循环中,data[k]和data[j]交换位置
        if( j + 1 < data.getSize() &&
           data.get(j + 1).compareTo(data.get(j)) > 0 )
            j ++;
        // data[j] 是 leftChild 和 rightChild 中的最大值

        if(data.get(k).compareTo(data.get(j)) >= 0 )
            break;

        data.swap(k, j);
        k = j;
    }
}

Replace

取出最大元素后，放入一个新元素
实现1：先extractMax ，再add，两次O(logn)操作
实现2：直接将堆顶元素替换后，Sift down ，一次O(logn)操作

// 查看堆中最大元素
public E findMax(){
    if(data.getSize() == 0)
        throw new IllegalArgumentException("Can not findMax when heap is empty.");
    return data.get(0);
}

// 取出堆中的最大元素，并且替换成元素e	
public E replace(E e){
    E ret = findMax();
    data.set(0, e);
    siftDown(0);
    return ret;
}

Heapify

将任意数组整理成堆的形状,不需要单独写成一个函数，可以单独放在一个新的堆的构造函数中
从最后一个非叶子节点进行操作
在自制的 ArrayList 中，增加构造函数

1
2
3

public Array(E[] arr){
    data = (E[])new Object[arr.length];
}

###复杂度

add 和 extractMax 时间复杂度都是 O(logn)
因为堆是一个完全二叉树，所以永远都不会退化为链表

优先队列（Priority-Queue）

普通队列：先进先出，后进后出
优先队列：出对顺序与进队顺序无关，和优先级相关

应用场景

医院：患者会动态增加，在其中选择优先级高的进行就诊
游戏AI：选择优先级高的玩家进行攻击

代码实现

和普通队列一样，继承队列接口，不过确认队首和出队的操作会有变化
实现方式有普通线性结构、顺序线性结构、堆三种实现方，堆最高效

// 堆实现优先队列
public class PriorityQueue<E extends Comparable<E>> implements Queue<E> {

    private MaxHeap<E> maxHeap;

    public PriorityQueue(){
        maxHeap = new MaxHeap<>();
    }

    public int getSize(){
        return maxHeap.size();
    }

    public boolean isEmpty(){
        return maxHeap.isEmpty();
    }

    public E getFront(){
        return maxHeap.findMax();
    }

    public void enqueue(E e){
        maxHeap.add(e);
    }

    public E dequeue(){
        return maxHeap.extractMax();
    }
}

比较器

自制优先队列

自制的优先队列内置的是最大堆，如果遇到取出某些问题需要内置最小堆怎么办？
其实最大和最小是可以相互转换的，那么我们先要创建一个频率类，

private class Freq implements Comparable<Freq>{

        public int e, freq;

        public Freq(int e, int freq){
            this.e = e;
            this.freq = freq;
        }

        @Override
        public int compareTo(Freq another){
            if(this.freq < another.freq)
                return 1;
            else if(this.freq > another.freq)
                return -1;
            else
                return 0;
        }
    }

Java优先队列

内置的优先队列比较高级，可以使用比较器
当然也可以直接将比较器匿名内部类的形式

热身练习

LeetCode-347