优先队列和堆

程序员文章站 2024-02-15 22:26:23

...

优先队列和堆

普通队列：先进先出，就像是我们在银行办业务或者是在超市买东西，但是考虑在医院，有病人有突发情况，这个时候容不得他去排队挂号了，这时他的优先级是比较高的，所以他需要得到优先的处理，像这种队列中的元素具有优先级的队列，我们把它称之为优先队列。在游戏中我们也会设置优先攻击血量最低的怪或者距离最近的怪，这时候血量和距离就成为了判断优先级的标准；在操作系统的任务调度，我们为程序分配CPU，内存等等资源，并不是先到先得的，也是根据程序的优先级来进行分配的。

堆的结构

这里的堆指的是二叉堆，它满足以下的性质

二叉堆是一棵完全二叉树
- 把元素顺序排列成树的形状

堆中某个节点的值总是不大于其父亲节点的值(最大堆，相应也可以定义最小堆)

如果我们使用数组去实现堆

上面的序号表示的是在数组中的下标，我们发现如果父节点的下标为i，那么左孩子的下标就为2i + 1，右孩子的下标为2i + 2，所以可以很快的根据父节点的下标得到左右孩子的下标，如果知道左右孩子的下标i，那么(i - 1)/2就可以得到父节点的下标(整数除法，小数部分会被舍去)。这个结论可以使用数学归纳法进行证明，但不是这里的重点，所以不多做阐述。

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 int size() {
        return data.getSize();
    }
    public boolean isEmpty() {
        return data.isEmpty();
    }
    
    //根据左右孩子的下标获得父亲节点的下标
    private int parent(int index) {
        return (index - 1) / 2;
    }
    //根据父节点的下标获得左孩子的下标
    private int leftChild(int index) {
        return 2 * index + 1;
    }
    //根据父节点的下标获得右孩子的下标
    private int rightChild(int index) {
        return 2 * index + 2;
    }
}

堆的实现

向堆中添加元素

public void swap(int i, int j) {
    if (i < 0 || i >= size() || j < 0 || j >= size()) {
        throw new IllegalArgumentException("参数错误");
    }
    E temp = data.get(i);
    data.set(i, data.get(j));
    data.set(j, temp);
}
public void add(E e) {
    data.addLast(e);
    siftUp(data.getSize() - 1);
}
private void siftUp(int index) {
    //index不是根节点(根节点不要上浮了) 并且孩子比父亲大
    while (index != 0 && data.get(index).compareTo(data.get(parent(index))) > 0) {
        swap(index, parent(index));
        index = parent(index);
    }
}

向堆中取出最大元素

public E findMax() {
    if (isEmpty()) {
        throw new IllegalArgumentException("堆为空");
    }
    return data.get(0);
}
public E extractMax() {
    E ret = findMax();
    swap(0,data.getSize() - 1);
    data.removeLast();
    siftDown(0);
    return ret;
}
private void siftDown(int index) {
    //没有孩子时，下沉结束
    while (leftChild(index) < size()) {
        int max = leftChild(index);
        int rightIndex = rightChild(index);
        if (rightIndex < size()) {
            max = data.get(max).compareTo(data.get(rightIndex)) > 0 ? max : rightIndex;
        }
        //最大孩子比父节点小时，下沉结束
        if (data.get(max).compareTo(data.get(index)) <= 0) {
            break;
        }
        swap(max,index);
        index = max;
    }
}

replace

replace操作指的是从堆中取出元素，并向堆中添加一个元素，实现的方法为

//取出堆中的最大元素，并添加一个新元素e
public E replace(E e) {
    E ret = findMax();
    data.set(0,e);
    siftDown(0);
    return ret;
}

heapify

heapify是指将任意一个数组整理成堆的形状，

我们把这个方法做成一个构造函数

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

完整代码

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.length);
        for (int i = 0; i < arr.length; i++) {
            data.addLast(arr[i]);
        }

        for (int i = parent(data.getSize() -1); i >=0; i--) {
            siftDown(i);
        }
    }

    public int size() {
        return data.getSize();
    }
    public boolean isEmpty() {
        return data.isEmpty();
    }

    //根据左右孩子的下标获得父亲节点的下标
    private int parent(int index) {
        return (index - 1) / 2;
    }
    //根据父节点的下标获得左孩子的下标
    private int leftChild(int index) {
        return 2 * index + 1;
    }
    //根据父节点的下标获得右孩子的下标
    private int rightChild(int index) {
        return 2 * index + 2;
    }

    public void swap(int i, int j) {
        if (i < 0 || i >= size() || j < 0 || j >= size()) {
            throw new IllegalArgumentException("参数错误");
        }

        E temp = data.get(i);
        data.set(i, data.get(j));
        data.set(j, temp);
    }

    public void add(E e) {
        data.addLast(e);
        siftUp(data.getSize() - 1);
    }
    private void siftUp(int index) {
        //index不是根节点(根节点不要上浮了) 并且孩子比父亲大
        while (index != 0 && data.get(index).compareTo(data.get(parent(index))) > 0) {
            swap(index, parent(index));
            index = parent(index);
        }
    }
    public E findMax() {
        if (isEmpty()) {
            throw new IllegalArgumentException("堆为空");
        }

        return data.get(0);
    }

    public E extractMax() {
        E ret = findMax();
        swap(0,data.getSize() - 1);
        data.removeLast();
        siftDown(0);
        return ret;
    }

    private void siftDown(int index) {
        //没有孩子时，下沉结束
        while (leftChild(index) < size()) {
            int max = leftChild(index);
            int rightIndex = rightChild(index);
            if (rightIndex < size()) {
                max = data.get(max).compareTo(data.get(rightIndex)) > 0 ? max : rightIndex;
            }
            //最大孩子比父节点小时，下沉结束
            if (data.get(max).compareTo(data.get(index)) <= 0) {
                break;
            }
            swap(max,index);
            index = max;
        }
    }

    //取出堆中的最大元素，并添加一个新元素e
    public E replace(E e) {
        E ret = findMax();

        data.set(0,e);
        siftDown(0);

        return ret;
    }
}

基于堆的优先队列

public class PriorityQueue<E extends Comparable<E>> implements Queue<E> {
    private MaxHeap<E> maxHeap;
    
    public PriorityQueue() {
        maxHeap = new MaxHeap<>();
    }
    
    @Override
    public void enqueue(E e) {
        maxHeap.add(e);
    }

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

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

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

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

优先队列和堆