优先级队列（堆）的详解

2023/11/30 9:15:12

优先级队列提供了两个最基本的操作：一个是返回最高优先级对象，一个是添加新的对象，优先级队列底层实现用到的数据结构就是堆

一、堆

1、堆的概念

如果有一个关键码的集合的所有元素按照完全二叉树的顺序存储方式存储在一个一维数组中，并满足ki <= k2i + 1且ki <= k2i + 2 (ki >= k2i + 1且ki >= k2i + 2 )，则称为小堆（或大堆）。根节点最大的堆为大根堆或者最大堆，根节点最小的堆为小根堆或最小堆

2、堆的存储方式

堆是一颗完全二叉树，因此可以层序的规则采用顺序的方式来高效存储

3、堆的创建

由于根节点的左右子树已经完全满足堆的性质，因此只需要将根节点向下调整好即可

private void createSort(int[] arr) {
        for (int parent = (arr.length - 2) / 2;parent >= 0;parent--) {
            shiftDowm(arr,parent,arr.length);
        }
    }

    private void shiftDowm(int[] arr, int parent, int length) {
        int child = parent * 2 + 1;
        while (child < length) {
            if ((child + 1) < length) {
                if (arr[child] < arr[child + 1]) {
                    child++;
                }
            }
            if (arr[parent] >= arr[child]) {
                break;
            }
            int tmp = arr[parent];
            arr[parent] = arr[child];
            arr[child] = tmp;
            parent = child;
            child = parent * 2 + 1;
        }
    }

注：建堆的复杂度为O(N)

4、堆的插入

总共需要两个步骤：

（1）先将元素放入底层空间中（空间不够时需要扩容）

（2）将最后新插入的节点向上调整，直到满足堆的性质

private void shiftUp(int child) {
        if (child >= size) {
            return;
        }
        int parent = (child - 1) / 2;
        while (child > 0 && parent > 0) {
            if (elementData[child] <= elementData[parent]) {
                break;
            }
            swap(elementData,parent,child);
            child = parent;
            parent = (child - 1) * 2;
        }
    }
private void swap(int[] elementData, int parent, int child) {
        int tmp = elementData[parent];
        elementData[parent] = elementData[child];
        elementData[child] = tmp;
    }

5、堆的删除

删除的一定是堆顶元素

步骤如下：

（1）将堆顶元素与堆中最后一个元素进行交换

（2）将堆中有效数据个数减少一个

（3）对堆顶元素进行向下调整

private int poll() {
        if (isEmpty()) {
            throw new RuntimeException("数组为空");
        }
        int value = elementData[0];
        swap(elementData,0,size - 1);
        size--;
        shiftDown(0);
        return value;
    }

6、用堆模拟实现优先级队列

import java.util.Arrays;

public class Heap {
    private int[] elementData;
    private int size;
    private int DEFAULT_CAPACITY = 10;

    public Heap() {
        this.elementData = new int[DEFAULT_CAPACITY];
        this.size = 0;
    }
    public Heap(int[] array) {
        this.elementData = Arrays.copyOf(array, array.length);
        this.size = array.length;
        int parent = (size - 1 - 1) / 2;
        for (int i = parent;i >= 0;i--) {
            shiftDown(i);
        }
    }
    private void shiftDown(int parent) {
        if (parent < 0) {
            return;
        }
        int child = parent * 2 + 1;
        while (child < size) {
            if (child + 1 < size) {
                if (elementData[child] < elementData[child + 1]) {
                    child++;
                }
            }
            if (elementData[parent]  > elementData[child]) {
                break;
            }
            swap(elementData,parent,child);
            parent = child;
            child = parent * 2 + 1;
        }

    }
    private void offer(int value) {
        if (isFull()) {
            elementData = Arrays.copyOf(elementData,elementData.length * 2);
        }
        elementData[size] = value;
        size++;
        shiftUp(size - 1);
    }
    private void shiftUp(int child) {
        if (child >= size) {
            return;
        }
        int parent = (child - 1) / 2;
        while (child > 0 && parent > 0) {
            if (elementData[child] <= elementData[parent]) {
                break;
            }
            swap(elementData,parent,child);
            child = parent;
            parent = (child - 1) * 2;
        }
    }
    private boolean isFull() {
        return size == elementData.length;
    }
    private int poll() {
        if (isEmpty()) {
            throw new RuntimeException("数组为空");
        }
        int value = elementData[0];
        swap(elementData,0,size - 1);
        size--;
        shiftDown(0);
        return value;
    }
    private int peek() {
        return elementData[0];
    }
    private boolean isEmpty() {
        return size == 0;
    }
    private void swap(int[] elementData, int parent, int child) {
        int tmp = elementData[parent];
        elementData[parent] = elementData[child];
        elementData[child] = tmp;
    }

    public static void main(String[] args) {
        int[] array = {27,15,19,18,28,34,65,49,25,37};
    }
}

二、优先级队列

1、优先级队列的特性