数据结构与算法之堆排序

堆是一种应用场景非常多的数据结构，最典型的莫过于堆排序，堆排序是基于堆结构实现的原地排序算法，它的时间复杂度是 O(nlogn)。虽然在实际开发中快排的性能要比堆排序优秀，但依然可以看到堆排序在一些经典场景中的应用，如优先队列、求 Top K 等。

想要了解堆结构和实际应用的同学们可通过本文获得以下分享：

1. 堆结构的基本介绍；
2. 堆的插入和删除操作；
3. 堆排序的算法内容；
4. 用堆排序求解一个 Top K 的问题。

“堆”是一种特殊的树，应用场景非常多，最经典的是堆排序。堆排序是一种原地的、时间复杂度为O(nlogn)的排序算法。

堆的性质

1. 结构性：堆是一个完全二叉树，完全二叉树要求树的节点从左到右排列，除最后一层外，每层的节点个数都是满的。
2. 堆序性：堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值。对于每个节点大于等于子节点值的堆称为大顶堆；每个节点小于等于子节点值的堆称为小顶堆。图1中只有（2）和 （4）满足堆的定义。

堆的存储

完全二叉树比较适合用数组来存储，除根节点外，节点i的左子节点的下标为i*2，右子节点的下标为i*2+1，父节点的坐标为i/2，根节点没有父节点，下标为0的空间暂时用不到。

堆的操作

堆最核心也是最基本的操作只有两个，即插入和删除，其它操作都属于扩展操作。堆的操作要满足结构性和堆序性才能结束，比如，在堆的最后插入了一个新的节点，该节点值小于其父节点的值，则需要将该节点与父节点交换，循环此过程，直到重新满足堆序性为止。我们以小顶堆为例，采用图解的方式来讲解堆的插入和删除操作。

插入（Insert）

删除（DeleteMin）

对于程序员来说，源码可能更直接，我们将插入和删除操作翻译成 Java 代码如下。

public class Heap {    private int[] a;    private int n;    private int count;    public Heap(int capacity) {        a = new int[capacity + 1];        n = capacity;        count = 0;    }    //插入    public void insert(int data) {        if (count >= n) return;        for (int i=++count; i/2 > 0 && a[i] < a[i/2]; i/=2) {            a[i/2] = a[i];        }    }    //删除     public int deleteMin() {        if (count == 0) return;        int result = a[1];        a[1] = a[count--];        heapify(a, count, 1);        return result;     }     private void heapify(int[] a, int n, int i) {        int top = a[i];        while (true) {            int minPos = 1;            if (i*2  a[i*2]) minPos = i*2;            if (i*2 + 1  a[i*2 + 1]) minPos = i*2 + 1;            if (minPos == i) break;            a[i] = a[minPos];            i = minPos;        }        a[i] = top;    }}

堆排序

借助于堆实现的排序算法称为堆排序，此排序方法的时间复杂度非常稳定，是O(nlogn)，并且它还是原地排序算法。本实例我们将使用堆排序对一个数组元素进行降序排序，可以把排序过程大致分解成两个大步骤，建堆和排序。

建堆

要实现堆排序，首先将包含n个数据的数组原地堆化。由于叶子节点无子节点，我们只需要从第一个非叶子节点开始往下堆化，堆化过程的分解图见图4。

翻译成代码如下：

private void buildHeap(int[] a, int n) {    for (int i = n/2; i >= 1; --i) {        headpify(a, n, i);    }}

在这段代码中，我们对下标从n/2开始到1的数据进行堆化，下标从n/2+1到n的节点都是叶子节点，不需要堆化。

排序

建堆结束后，数组中的数据已经是按照小顶堆的特性来组织的，数组中的第一个元素是堆顶，也是最小的元素。我们把它跟最后一个元素交换，那最小元素就放到了下标为n的位置。

这个过程有点类似堆的删除操作，当堆顶元素删除后，我们把下标为n的元素放到堆顶，然后再通过堆化的方法，将剩下的n-1个元素重新构建成堆。堆化完成后，我们再取堆顶的元素，放到下标为n-1的位置，一直重复这个过程，直到最后堆中只剩下下标为一的一个元素，排序工作就完成了。翻译成代码如下。

public void sort(int[] a, int n) {    buildHeap(a, n);    int k = n;    while (k > 1) {        int temp = a[1];        a[1] = a[k];        a[k] = temp;        --k;        heapify(a, k, 1);    }}

一般而言，对数组进行升序排序会构建大顶堆；对数组进行降序排序会构建小顶堆。

求 Top K

在一个包含n个数据的数组中查找前K大数据，我们可以维护一个大小为K的小顶堆，顺序遍历数组，从数组中取出数据与堆顶元素比较。如果比堆顶元素大，我们就把堆顶元素删除，并且将这个元素插入到堆中；如果比堆顶元素小，就不作处理。遍历完成后，小顶堆中存储的就是前 K 大数据，当然，如果希望对 TopK 进行排序，还要做进一步的排序处理。

小结

在本文中，我们从堆的基础结构聊起，堆是一种完全二叉树，最适合用数组存储，每个节点的值都大于等于或小于等于其子树节点的值，这一点大家其实可以和二叉查找树进行比较来看。

堆中基础的两个操作是数据插入和删除，它们是堆排序的实现基础，它们的时间复杂度都是O(logn)。堆排序就是建堆和排序，如果是升序，适合构建大顶堆来实现；如果是降序，则适合用小顶堆。

另外，我们也补充说明了堆排序在求Top K 中的实际应用，大家可以根据我的描述尝试用自己熟悉的语言去实现，后期我也会把我的代码放到 GitHub 上供大家比较。

本文首发于 GitChat，未经授权不得转载，转载需与 GitChat 联系。

阅读全文: http://gitbook.cn/gitchat/activity/5ca6ce974bab9754d058dd4e

您还可以下载 CSDN 旗下精品原创内容社区 GitChat App ，阅读更多 GitChat 专享技术内容哦。