算法笔记 -- 堆和堆排序

之前一直对堆这个数据结构和堆排序不太了解,今天正好在leetcode上写题的时候又复习了一遍,在这里记录一下堆和堆排序。

堆

堆是一种特殊的二叉树，在一些语言中也称为优先队列。满足以下的性质：

• 堆是一棵完全二叉树，除了最后一层，其他层的节点都是满的，最后一层从左部开始连续；

• 堆的每一个节点的值都大于（大根堆）或小于（小根堆）它的左右子树的值；

  

  堆不像$BST$一样严格，只要求某个节点的值比它的左子树右子树都更大或更小就可以，所以同一组数据，可以构建出多种形态的堆。

  

堆大部分情况下都用数组来表示

如上图所示，比较容易地可以发现规律，对于数组中索引为$i$地根节点，它的左子树索引为$2\times i+1$，右子树的索引为$2\times i+2$。

对于一个索引为$i$的节点，它的父节点索引为$floor((i-1)/2)$，向下取整。

堆的操作

堆的操作主要包括插入和删除。由于插入和删除后都可能不再满足堆的性质，所以在插入或删除之后都要对堆进行调整，这个过程也称为$heapify$。

堆化

堆化$heapify$包括从下往上的上浮过程和从上往下的下降过程。

上浮过程是当前元素不断向上和父节点比较大小：

对于大根堆，当前元素比父节点大，交换，让大的节点上去，对于小根堆，当前元素比父节点小，交换，让小的节点上去。

下沉过程是当前元素不断向下比较和两个孩子的大小关系：

对于大根堆，当前元素和孩子中较大的比较，比子节点小就交换，让小的下去，对于小根堆，当前元素和孩子中较小的比较，比子节点大就交换，让大的节点下去。

插入

因为要满足完全二叉树的条件，所以在数组的末尾插入元素，再进行堆化。

让新插入的结点和父节点比较大小，如果新插入的结点大于父节点，则交换，一直重复到满足堆的条件。

删除

堆顶元素存储的就是堆中数据最大的或最小的，删除了堆顶元素之后，可以把最后一个元素移到根节点的位置，这样就可以满足完全二叉树的性质，再进行堆化。

最后一个节点放到堆顶，在子节点中找出较大(大顶堆)的那个对比。小于子节点时，互换两个节点，并且重复进行这个过程。

建堆

建立堆有两种方式，一种是从前往后，一种是从后往前。

从前往后依次处理数组，数据插入到堆中时，不借助另一个数组，直接在原数组上操作，采用从下往上的堆化，直到最后一个元素处理完成。这样处理的话，除了第一个节点不需要堆化，其他都需要堆化，对$n-1$个节点进行了堆化。

从后往前处理数组，使用从上往下堆化，直到第一个元素处理完成。对于完全二叉树来说，下标$n/2+1$到$n$的节点都是叶子节点，没有子树，所以可以直接从$n/2$开始。

复杂度分析

堆化的过程就是顺着节点所在的路径开始交换的，所以堆化的时间复杂度和树的高度成正比，所以为$O(logn)$。

插入和删除的时间复杂度也主要取决于堆化，所以时间复杂度为$O(logn)$。

建堆的过程中，由于叶子节点不需要堆化，所以堆化的节点从倒数第二层开始，每个节点堆化的过程中，需要比较和交换的节点个数是和高度成正比的。

所以建堆的时间复杂度为$O(n)$。

堆排序

堆排序是建立在一个堆的基础上的，数组的第一个元素就是堆顶，也就是最大或最小的那个元素，我们可以利用删除堆顶的思路来进行堆排序。

排序过程中需要对$n$个元素进行堆化，堆化的时间复杂度为$O(logn)$，所以排序的时间复杂度为$O(nlogn)$。

若是对大顶堆进行堆排序，则会得到一个升序数组，因为每次最大的元素都往后面移动，小顶堆排序得到降序数组。

堆排序不需要开辟额外空间，需要交换元素时的一个临时变量，所以空间复杂度为$O(1)$。

堆的应用

优先队列

普通的队列的出队顺序取决于入队顺序，优先队列的出队顺序取决于元素的优先级，可以理解为优先队列就是一个排序后的队列。堆是实现优先队列最直接的方式。因为堆和优先队列十分相似。

例如在实现定时器时，如果使用普通的队列，就需要不断轮询时间，扫描一趟任务列表，看看是否有任务到达设定的执行时间，到达了就开始执行这个任务。但是这样实现会导致很多躺扫描其实是不必要的，而且每次轮询如果任务列表比较大，耗时也会比较长。

如果使用优先队列，可以根据任务设定的执行时间，将这些任务存储在一个优先队列中，堆顶存储的是最先执行的任务，拿队首的任务的执行时间点，与当前时间点相减，就可以得到下一次执行任务的时间，这样也省去了这段时间的轮询。这段时间间隔过去后，取出堆顶，再重新计算堆顶即可。

TopK

在一堆数据里找到前K大的数。

因为取前3大的元素是降序排序，所以可以使用小顶堆来求解。

例如求数组$[4,5,3,7,1,8]$中的前3大元素。

Setp1:取前3大元素是降序，所以选择小堆顶。取出前三个数组[4，5，3]，建小顶堆，得到 [3，4，5]；

Setp2:遍历数组到元素7，比堆顶元素3大，将3移除，将7放入堆中，堆化后，小顶堆变为 [4，5，7]

Setp3:接着遍历数组到元素1，比堆顶元素4小，不处理

Setp4:接着遍历数组到元素8，比堆顶元素4大，将4移除，将8放入堆中，堆化后，小顶堆变为 [5，8，7]，此时遍历结束，顶堆中的元素就是前 3 大元素

求动态数据集合中的中位数

维护两个堆，一个大顶堆，一个小顶堆。

n 个数据，n 是偶数。前 n/2 个数据存储在大顶堆中，后 n/2 个数据存储在小顶堆中，保证小顶堆中的数据都大于大顶堆中的数据，此时的中位数就是大根堆的堆顶元素和小根堆的堆顶元素相加除以2。

n 是奇数。大顶堆就存储 n/2+1 个数据，小顶堆中就存储 n/2 个数据，此时的中位数就是大根堆的堆顶。

新添加一个数据的时候，如果新加入的数据小于等于大顶堆的堆顶元素，将这个新数据插入到大顶堆；否则，将这个新数据插入到小顶堆。

两个堆中的数据个数不符合约定数量时,数量少的堆将堆顶元素移动到另一个堆，直至平衡。

堆的代码实现（Java）

JAVA 复制

public class Heap {
    private int[] heap;
    private int heapSize;

    /**
     * 初始化堆
     *
     * @param capacity 堆的容量
     */
    public Heap(int capacity) {
        this.heapSize = 0;
        this.heap = new int[capacity + 1];
        Arrays.fill(heap, 0);
    }

    /**
     * 判断堆是否为空
     *
     * @return
     */
    public boolean isEmpty() {
        return heapSize == 0;
    }

    /**
     * 判断堆是否为满
     *
     * @return
     */
    public boolean isFull() {
        return this.heapSize == this.heap.length;
    }

    /**
     * 返回i节点下标的父节点下标,数组下标从0开始
     *
     * @param i
     * @return
     */
    private int parent(int i) {
        return (i - 1) / 2;
    }

    /**
     * 返回堆顶元素
     *
     * @return
     */
    public int heapTop() {
        if (isEmpty()) {
            throw new NoSuchElementException("堆为空");
        }
        return heap[0];
    }

    /**
     * 添加元素
     *
     * @param val
     */
    public void insert(int val) {
        if (isFull()) {
            throw new NoSuchElementException("堆已满");
        }
        heap[heapSize++] = val;
        // 向上调整(维护堆结构)
        heapifyUp(heapSize - 1);
    }

    /**
     * 删除堆中下标为i的元素
     *
     * @param i
     * @return
     */
    public int remove(int i) {
        if (isEmpty()) {
            throw new NoSuchElementException("堆为空");
        }
        int ret = heap[i];
        // 用末尾的元素覆盖要删除的元素
        heap[i] = heap[heapSize - 1];
        heapSize--;
        heapifyDown(i);
        return ret;
    }

    /**
     * 向上维护堆
     *
     * @param i
     */
    private void heapifyUp(int i) {
        int insertVal = heap[i];
        while (i > 0 && insertVal > heap[parent(i)]) {
            heap[i] = heap[parent(i)];
            i = parent(i);
        }
        heap[i] = insertVal;
    }

    /**
     * 返回左右子下标中较大的下标
     *
     * @param i
     * @return
     */
    private int maxChild(int i) {
        int leftChild = (2 * i + 1);
        int rightChild = (2 * i + 2);
        return heap[leftChild] > heap[rightChild] ? leftChild : rightChild;
    }

    /**
     * 向下交换进行维护
     *
     * @param i
     */
    private void heapifyDown(int i) {
        int child;
        // 保存要交换前i下标对应的值
        int temp = heap[i];
        // 当数组未越界，维护堆（如果左右子下标中较大的子下标的值大于父下标，则它们进行交换。)
        while ((2 * i + 1) < heapSize) {
            child = maxChild(i);
            if (temp >= heap[child]) {
                break;
            }
            heap[i] = heap[child];
            i = child;
        }
        heap[i] = temp;
    }
}