二叉堆的应用：优先队列和堆排序（解释+java代码）

文章目录

• • • • 一、二叉堆
      • 二、相关操作
      • • 2.1 插入节点
        • 2.2 删除节点
        • 2.3 构建二叉堆
      • 三、优先队列
      • 四、堆排序
      • 五、其余补充

学习自书籍——《小灰的算法之旅》~

一、二叉堆

二叉堆本质上是一种完全二叉树，分为大根堆和小根堆两类：

• 大根堆：任何一个父结点的值都大于或等于它左、右孩子结点的值
• 小根堆：任何一个父结点的值都小于或等于它左、右孩子结点的值

二叉堆的根结点叫做堆顶，因此，大根堆的堆顶是整个堆中的最大元素、小根堆的堆顶是整个堆中的最小元素。

应用：堆排序、优先队列。

二、相关操作

2.1 插入节点

当二叉堆插入节点时，插入位置是完全二叉树的最后一个位置。紧接着，需要做一系列“上浮”操作：（以大根堆为例）将最后一个位置的结点依次与它的父节点进行比较，如果大于父节点，则和父节点交换位置，继续这个操作，直到到达堆顶位置。

用到以下二叉树的性质：

• 假设父节点的下标是

  parent

  ，那么它的左孩子下标就是

  2\*parent+1

  ，右孩子下标就是

  2*\parent+2

• 假设孩子节点的下标是

  child

  ，那么它的父节点下标就是

  (child - 1)/2

以优先队列的“上浮”操作代码为例（其中size表示此时队列中的元素个数）：

private void upAdjust() {
    int childIndex = size - 1;
    int parentIndex = (childIndex - 1) / 2;
    int temp = array[childIndex];//使用中间变量，可以做到单向覆盖，循环结束后将其存入交换后的最终位置即可。
    while (childIndex > 0 && array[childIndex] > array[parentIndex]) {
        array[childIndex] = array[parentIndex];
        childIndex = parentIndex;
        parentIndex = (childIndex - 1) / 2;
    }
    array[childIndex] = temp;
}
           

2.2 删除节点

二叉堆删除节点的过程和插入节点的过程正好相反，所删除的是处于堆顶的节点。需要以下几步：

1. 删除堆顶节点；
2. 将最后一个节点临时补充到堆顶；
3. “下沉”操作（和插入时的“上浮”操作相反）：让暂存在堆顶位置的节点和他的左右孩子依次比较，如果左右孩子节点中最小的一个比其小，则让堆顶节点下沉，不断重复这个过程。
4. 由此，二叉堆重新得到了调整。

以优先队列的“下沉”操作代码为例（其中size表示此时队列中的元素个数）：

private void downAdjust() {
    int parentIndex = 0;
    int childIndex = 1;
    int temp = array[parentIndex];
    while (childIndex <= size - 1) {
        if (array[2 * parentIndex + 2] > array[2 * parentIndex + 1]) {
            childIndex++;
        }
        if (array[parentIndex] >= array[childIndex]) {
            break;
        }
        array[parentIndex] = array[childIndex];
        parentIndex = childIndex;
        childIndex = 2 * parentIndex + 1;
    }
    array[parentIndex] = temp;
}
           

2.3 构建二叉堆

构建二叉堆就是把一个无序的完全二叉树调整为二叉堆，本质是让所有非叶节点依次”下沉“。

首先从最后一个非叶节点开始，如果总节点数为

size

，那么其下标就是

(size-2)/2

，紧接着依次

-1

继续进行“下沉”操作…

经过多次比较和“下沉”操作，最终每一节点都小于他的左、右孩子节点，构建完成。

public static void buildHeap(int[] array) {
    for (int i = (array.length - 2) / 2; i >= 0; i--) {
        downAdjust(array, i, array.length);
    }
}
           

三、优先队列

队列：先进先出（FIFO）。

优先队列分为两种：

• 最大优先队列：无论入队顺序如何，都是当前最大元素优先出队
• 最小优先队列：无论入队顺序如何，都是当前最小元素优先出队

要实现这个需求，利用线性数据结构也可以实现，但是时间复杂度较高。

因此，可以使用二叉堆实现：入队即插入、出队即删除。

import java.util.Arrays;

/**
 * @author 刘星宇
 * @version 1.0
 * @date 2021/4/24 14:29
 */
public class PriorityQueue {

    private int[] array;
    private int size;

    public PriorityQueue(int capcity) {
        this.array = new int[capcity];
    }

    public void resize() {
        int newSize = this.size * 2;
        this.array = Arrays.copyOf(array, newSize);
    }

    public void enQueue(int key) {
        if (size > array.length) {
            resize();
        }
        array[size++] = key;
        upAdjust();
    }

    public int deQueue() throws Exception {
        if (size <= 0) {
            throw new Exception("该队列为空！");
        }
        int res = array[0];
        array[0] = array[size - 1];
        size--;
        downAdjust();
        return res;
    }

    private void upAdjust() {
        int childIndex = size - 1;
        int parentIndex = (childIndex - 1) / 2;
        int temp = array[childIndex];
        while (childIndex > 0 && array[childIndex] > array[parentIndex]) {
            array[childIndex] = array[parentIndex];
            childIndex = parentIndex;
            parentIndex = (childIndex - 1) / 2;
        }
        array[childIndex] = temp;
    }

    private void downAdjust() {
        int parentIndex = 0;
        int childIndex = 1;
        int temp = array[parentIndex];
        while (childIndex <= size - 1) {
            if (array[2 * parentIndex + 2] > array[2 * parentIndex + 1]) {
                childIndex++;
            }
            if (array[parentIndex] >= array[childIndex]) {
                break;
            }
            array[parentIndex] = array[childIndex];
            parentIndex = childIndex;
            childIndex = 2 * parentIndex + 1;
        }
        array[parentIndex] = temp;
    }


    public static void main(String[] args) throws Exception {
        PriorityQueue priorityQueue = new PriorityQueue(32);
        priorityQueue.enQueue(3);
        priorityQueue.enQueue(5);
        priorityQueue.enQueue(10);
        priorityQueue.enQueue(7);
        priorityQueue.enQueue(6);
        priorityQueue.enQueue(9);
        priorityQueue.enQueue(-1);
        System.out.println(Arrays.toString(priorityQueue.array));
        System.out.println("出队元素:" + priorityQueue.deQueue());
        System.out.println("出队元素:" + priorityQueue.deQueue());
        System.out.println("出队元素:" + priorityQueue.deQueue());
    }
}
           

四、堆排序

二叉堆的构建、删除、自我调整等基本操作，正是实现堆排序的基础。

由于二叉堆的特性，每一次删除旧堆项，调整后的新堆项都是大小仅次于旧堆项的节点。那么只要反复删除堆顶，反复调整二叉堆，所得到的集合就会成为一个有序集合。

算法步骤：

1. 把无序数组构建成二叉堆。需要从小到大排序，则构成大根堆；需要从大到小排序，则构成小根堆。
2. 循环删除堆顶元素，替换到二叉堆的末尾，调整堆产生新的堆项。

其中大部分操作和上述类似，区别仅在步骤2：

public void buildHeap(int[] array) {
    for (int i = (array.length - 2) / 2; i >= 0; i--) {
        downAdjust(array, i, array.length);
    }
    System.out.println(Arrays.toString(array));
    //循环删除堆顶元素，移到集合尾部，调整堆产生新堆项
    for (int i = array.length - 1 ; i>0;i--){
        int temp = array[i];
        array[i] = array[0];
        array[0] = temp;
        //下沉，调整大根堆
        downAdjust(array, 0, i);
    }
}
           

也可以使用优先队列依次出队实现堆排序。

五、其余补充

• 二叉堆的插入和删除操作时间复杂度是O(logn)，但构建堆的时间复杂度是O(n)；
• 二叉堆虽然是一个完全二叉树，但他的存储方式不是链式存储，而是顺序存储；
• 优先队列入队和出队的时间复杂度都是O(logn)；
• 堆排序时间复杂度：O(nlogn)、空间复杂度O(1)；
• 堆排序是不稳定排序；