当前位置：首页 > article >正文

数据结构与算法-05堆优先队列-02

article 2024/12/22 9:57:59

堆的时间复杂度

如下图所示，调整元素72到达堆顶(最大堆)，一共进行了2次交换。

从层的角度分析

堆的高度为h,进行上浮(floatUp) 和下沉(swimDown)操作最大时间与层级(高度h)有关，时间复杂度O(h)。

从节点数量分析

堆是一颗完全二叉树，完全二叉树的时间复杂度与节点有关: O(log₂n),此处n为二叉树的节点数量。

Heapify(堆化)

什么是heapify

【Heapify is the process of creating a heap data structure from a binary tree. It is used to create a Min-Heap or a Max-Heap. Heapify是将heap调整为最大堆或最小堆的过程，我们以最大堆为例，演示调整过程。

heapify的实现过程

找到最后一个非叶子节点

在二叉堆的数组表示中，如果堆的大小（即数组中元素的数量）为size，那么最后一个非叶子节点的索引就是size / 2 - 1。因为从size / 2开始，数组中的元素都是叶子节点，它们没有子节点，所以不需要进行heapify操作

找到左子节点，右子节点

假设插入heapify中的是父节点，算出其左、右子节点索引

//记录当前节点为最高值节点
int highIndex = currIndex;
int leftIndex = 2 * currIndex + 1;
int rightIndex = 2 * currIndex + 2;

更新左、右子节点的最大值

//更新左、右节点的最大值
if (leftIndex < size && data[leftIndex] > data[hightIndex]) highIndex = leftIndex;
if (rightIndex < size && data[rightIndex] > data[highIndex]) highIndex = rightIndex;

交换当前值与左右子节点最大值

//交换最大值索引
if (highIndex != currIndex) {
    T tmp = data[highIndex];
    data[highIndex] = data[currIndex];
    data[currIndex] = tmp;
    heapify(highIndex);
}

传入数组通过heapify进行调整为堆

public MyHeap(Integer[] data) {
    this.data = data;
    this.size = data.length;
    //在二叉堆的数组表示中，如果堆的大小（即数组中元素的数量）为size，
    // 那么最后一个非叶子节点的索引就是size / 2 - 1。因为从size / 2开始，
    // 数组中的元素都是叶子节点，它们没有子节点，所以不需要进行heapify操作
    for (int i = size / 2 - 1; i >= 0; i--) {
        heapify(i);
    }
}

heapify的时间复杂度

如果使用offer()添加

一个数据进行堆化时间复杂度为logn, 如果多个数据按照这样添加时间复杂度: nlogn

快速堆化过程

计算heapify的平均时间复杂度

时间复杂度 = 求和(每层节点数 * 移动数)

Heapify的时间复杂度: O(n)

替换堆顶(replace)

替换堆顶元素,将堆顶替换，swim堆。

public void replace(T newVal) {
    if (isEmpty()) {
        return;
    }
    data[0] = newVal;
    swim(0);
}

优先队列(PriorityQueue)

Java PriorityQueue类是一种队列数据结构实现，其中根据优先级处理对象。它与遵循FIFO（先进先出）算法的标准队列不同。

在优先级队列中，添加的对象根据其优先级。默认情况下，优先级由对象的自然顺序决定。队列构建时提供的比较器可以覆盖默认优先级。

PriorityQueue特性

java 的PriorityQueue是最小堆

List<Integer> list = new ArrayList<>();
list.add(56);
list.add(25);
list.add(30);
list.add(70);

PriorityQueue<Integer> queue
        = new PriorityQueue<>();
queue.addAll(list);
System.out.println(queue);

运行结果

[25, 56, 30, 70]

修改为最大堆

List<Integer> list = new ArrayList<>();
list.add(56);
list.add(25);
list.add(30);
list.add(70);

PriorityQueue<Integer> queue
        = new PriorityQueue<>(Comparator.reverseOrder());
queue.addAll(list);
System.out.println(queue);