拜托，别再问我什么是堆了!

作者 | 码海

来源 | 码海（ID：seaofcode）

堆是生产中非常重要也很实用的一种数据结构，也是面试中比如求 Top K 等问题的非常热门的考点，本文旨在全面介绍堆的基本操作与其在生产中的主要应用，相信大家看了肯定收获满满！

本文将会从以下几个方面来讲述堆:

• 生产中的常见问题

• 堆的定义

• 堆的基本操作

• 堆排序

• 堆在生产中应用

我们在生产中经常碰到以下常见的问题：

1. 优先级队列的应用场景很广，它是如何实现的呢

2. 如何求 Top K 问题

3. TP99 是生产中的一个非常重要的指标，如何快速计算

可能你已经猜到了，以上生产上的高频问题都可以用堆来实现，所以理解堆及掌握其基本操作十分重要！接下来我们就来一步步地来了解堆及其相关操作，掌握了堆，上面三个生产上的高频问题将不是问题。

堆的定义

堆有以下两个特点：

1. 堆是一颗完全二叉树，这样实现的堆也被称为二叉堆

2. 堆中节点的值都大于等于（或小于等于）其子节点的值，堆中如果节点的值都大于等于其子节点的值，我们把它称为大顶堆，如果都小于等于其子节点的值，我们将其称为小顶堆。

简单回顾一下什么是完全二叉树，它的叶子节点都在最后一层，并且这些叶子节点都是靠左排序的。

从堆的特点可知，下图中，1，2 是大顶堆，3 是小顶堆， 4 不是堆（不是完全二叉树）

从图中也可以看到，一组数据如果表示成大顶堆或小顶堆，可以有不同的表示方式，因为它只要求节点值大于等于（或小于等于）子节点值，未规定左右子节点的排列方式。

堆的底层是如何表示的呢，从以上堆的介绍中我们知道堆是一颗完全二叉树，而完全二叉树可以用数组表示：

如图示：给完全二叉树按从上到下从左到右编号，则对于任意一个节点来说，很容易得知如果它在数组中的位置为 i，则它的左右子节点在数组中的位置为 2i，2i + 1，通过这种方式可以定位到树中的每一个节点，从而串起整颗树。

一般对于二叉树来说每个节点是要存储左右子节点的指针，而由于完全二叉树的特点（叶子节点都在最后一层，并且这些叶子节点都是靠左排序的），用数组来表示它再合适不过，用数组来存储有啥好处呢，由于不需要存指向左右节点的指针，在这颗树很大的情况下能省下很多空间！

堆的基本操作

堆有两个基本的操作，构建堆（往堆中插入元素）与删除堆顶元素，我们分别来看看这两个操作

• 往堆中插入元素

往堆中插入元素后（如下图示），我们需要继续满足堆的特性，所以需要不断调整元素的位置直到满足堆的特点为止（堆中节点的值都大于等于（或小于等于）其子节点的值）,我们把这种调整元素以让其满足堆特点的过程称为堆化（heapify）

由于上图中的堆是个大顶堆，所以我们需要调整节点以让其符合大顶堆的特点。怎么调整？不断比较子节点与父节点，如果子节点大于父节点，则交换，不断重复此过程，直到子节点小于其父节点。来看下上图插入节点 11 后的堆化过程

这种调整方式是先把元素插到堆的最后，然后自下而上不断比较子节点与父节点的值，我们称之为由下而上的堆化。有了以上示意图，不难写出插入元素进行堆化的代码：

public class Heap {
    private int[] arr;       // 堆是完全二叉树，底层用数组存储
    private int capacity;    // 堆中能存储的最大元素数量
    private int n;          // 当前堆中元素数量

    public Heap(int count) {
        capacity = count;
        arr = new int[capacity+1];
        n = 0;
    }

    public void insert(int value) {
        if (n >= capacity) {
            // 超过堆大小了，不能再插入元素
            return;
        }
        n++;
        // 先将元素插入到队尾中
        arr[n] = value;

        int i = n;
        // 由于我们构建的是一个大顶堆，所以需要不断调整以让其满足大顶堆的条件
        while (i/2 > 0 && arr[i] > arr[i/2]) {
            swap(arr, i, i/2);
            i = i / 2;
        }
    }
}

时间复杂度就是树的高度，所以为 O(logn)。

• 删除堆顶元素

由于堆的特点（节点的值都大于等于（或小于等于）其子节点的值），所以其根节点（堆项）要么是所有节点中最大，要么是所有节点中最小的，当删除堆顶元素后，也需要调整子节点，以让其满足堆（大顶堆或小顶堆）的条件。

假设我们要操作的堆是大顶堆，则删除堆顶元素后，要找到原堆中第二大的元素以填补堆顶元素，而第二大的元素无疑是在根节点的左右子节点上，假设是左节点，则用左节点填补堆顶元素之后，左节点空了，此时需要从左节点的左右节点中找到两者的较大值填补左节点...，不断迭代此过程，直到调整完毕，调整过程如下图示：

但是这么调整后，问题来了，如上图所示，在最终调整后的堆中，出现了数组空洞，对应的数组如下：

怎么解决？我们可以用最后一个元素覆盖堆顶元素，然后再自上而下地调整堆，让其满足大顶堆的要求，这样即可解决数组空洞的问题。

看了以上示意图，代码实现应该比较简单，如下：

/**
 * 移除堆顶元素
 */
public void removeTopElement() {
    if (n == 0) {
        // 堆中如果没有元素，也就是不存在移除堆顶元素的情况了
        return;
    }
    int count = n;
    arr[1] = arr[count];
    --count;
    heapify(1, count);
}

/**
 * 自上而下堆化以满足大顶堆的条件
 */
public void heapify(int index, int n) {

    while (true) {
        int maxValueIndex = index;
        if (2 * index