力扣labuladong一刷day56天二叉堆实现优先级队列

2024-01-09 16:42:28

力扣labuladong一刷day56天二叉堆实现优先级队列

一、二叉堆实现优先级队列

二叉堆就是大顶堆或者小顶堆,底层结构采用数组,从索引1开始,i2是左孩子,i2+1是右孩子,i/2是父节点。
二叉堆一般有三个操作:

  • 获取元素:获取堆顶元素
  • 添加元素:追加到数组尾部,然后通过上浮操作使其到正确位置。
  • 删除元素:删除只能删除堆顶元素,具体操作是,把堆顶元素与数组尾部元素对换,删掉尾部,然后再把堆顶元素下沉到正确位置。
    其中,上浮是在添加元素中使用,只需要和父节点比较大小即可。下沉是在删除元素中使用,这时就需要从两个子节点中选择最大的进行替换。
class MaxPQ {

    int[] pq;
    int size = 0;

    public MaxPQ(int cap) {
        pq = new int[cap+1];
    }

    public int getMax() {
        return pq[1];
    }

    public void add(int v) {
        pq[++size] = v;
        up(size);
    }

    public int delMax() {
        int t = getMax();
        swap(1, size);
        pq[size] = 0;
        size--;
        down(1);
        return t;
    }

    private void up(int x) {
        while (x > 1 && pq[x] > pq[parent(x)]) {
            swap(x, parent(x));
            x = parent(x);
        }
    }

    private void down(int x) {
        while (x*2 <= size) {
            int leftIndex = x*2;
            int rightIndex = x*2+1;
            if (rightIndex <= size && pq[rightIndex] > pq[leftIndex]) {
                leftIndex = rightIndex;
            }
            if (pq[x] >= pq[leftIndex])break;
            swap(x, leftIndex);
            x = leftIndex;
        }
    }

    private int parent(int x) {
        return x/2;
    }

    private void swap(int x, int y) {
        int temp = pq[x];
        pq[x] = pq[y];
        pq[y] = temp;
    }
}

文章来源:https://blog.csdn.net/qq_43511039/article/details/135477364
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。