算法导论笔记之堆排序

---

堆

在介绍堆排序之前，首先让我们了解一下什么是“堆”。

堆是一种数据结构，可以看成是一种特殊的完全二叉树。堆具有两种形式：每个结点的值大于或等于其左右孩子结点的堆称为最大堆，每个结点的值小于或等于其左右孩子结点的堆称为最小堆。如下图所示，分别是一个最大堆和最小堆。

我们将堆的结点从上到下，从左到右编号（从1开始编号）。然后我们就可以将堆存储在一个数组中。需要注意的是，这个数组的下标是从1开始的，而不是从0开始的。

通过观察可以发现堆的一个重要性质：如果一个结点在数组中的下标为i，那么这个结点的左子结点的下标为2 * i，右子结点的下标为2 * i + 1。

---

维护堆的性质

下面我们讨论如何维护最大堆的性质，维护最小堆的性质的操作与最大堆相似。

根据堆的性质我们知道，堆的每一个子树都是一个堆。如果一个完全二叉树的两个子树都满足最大堆的性质，但是这个根结点的两个子结点的值并不都小于或等于根结点的值，那么就违反了最大堆的性质。我们需要调整根结点的位置使整个完全二叉树符合最大堆的性质。

如下图（a）所示，以结点2为根结点的完全二叉树的两个子树是两个最大堆，但是结点2的值比它的子结点的值小，所以以结点2为根结点的完全二叉树不是最大堆。我们需要调整结点的位置，使整个完全二叉树符合最大堆的性质。如图（c）所示。

要使这个二叉树符合最大堆的性质，可以先把结点2与它的两个子结点中最大的结点交换位置。但是交换后二叉树的两个子树又不一定符合最大堆的性质（如图（b）所示）。所以再递归地交换结点4与它的最大子结点的位置。最后就可以使整个二叉树都符合最大堆的性质。

下面用C语言实现了维护最大堆的函数：

#define LEFT(index) (index * 2)      // 返回左孩子的下标
#define RIGHT(index) (index * 2 + 1) // 返回右孩子的下标

void maxHeapify(int heap[], int heapSize, int index)
{
   
    int left = LEFT(index);
    int right = RIGHT(index);
    int largest;

    if (left <= heapSize && heap[left - 1] > heap[index - 1])
    {
   
        largest = left;
    }
    else
    {
   
        largest = index;
    }

    if (right <= heapSize && heap[right - 1] > heap[largest - 1])
    {
   
        largest = right;
    }

    if (largest != index)
    {
   
        int temp = heap[index - 1];

        heap[index - 1] = heap[largest - 1];
        heap[largest - 1] = temp;
        maxHeapify(heap, heapSize, largest);
    }

    return;
}

---

建堆

在这一节中，我们介绍如何将一个完全二叉树构建成堆（以最大堆为例）。

在上一节中，我们实现了一个maxHeapify函数。当一个二叉树的两个子树是最大堆时，我们可以调用maxHeapify函数将整个二叉树转换为最大堆。而对于一个普通的完全二叉树，我们可以自底向上利用maxHeapify构建最大堆。

由于在一个大小为heapSize的数组中，下标大于heapSize / 2的结点没有子结点，所以我们将下标从heapSize / 2到1依次传入maxHeapify即可。

以下是C语言实现：

void buildMaxHeap(int heap[], int heapSize)
{
   
    for (int i = heapSize / 2; i >= 1; i--)
    {
   
        maxHeapify(heap, heapSize, i);
    }

    return;
}

---

堆排序算法

我们通过建堆函数buildMaxHeap将一个无序数组转化为一个最大堆。由于在最大堆中的每一个结点的值都大于它的两个子结点，所以最大堆的根结点就是这个堆中所有结点中值最大的结点。也就是说，存储最大堆的数组的第一个元素是这个数组中的最大值。我们将数组中的第一个元素与最后一个元素交换，然后调用函数buildMaxHeap对这个数组的前heapSize - 1个元素进行建堆。那么这个数组的第一个元素就是前heapSize - 1个元素的最大值。再将第一个元素与倒数第二个元素交换。逐步缩小堆的大小，重复建堆和交换这两个步骤，最终我们就将这个数组排序完成，这就是堆排序算法。

void heapSort(int array[], int arraySize)
{
   
    for (int i = arraySize; i >= 2; i--)
    {
   
        buildMaxHeap(array, i);

        int temp = array[0];

        array[0] = array[i - 1];
        array[i - 1] = temp;
    }

    return;
}

---

优先队列

堆排序是一个很优秀的算法（时间复杂度是O(nlgn)），但是快速排序在一般情况下比堆排序的效率更高。尽管如此，堆也有很多用途。堆的一个常见应用就是优先队列。与堆相同，优先队列也有两种：最大优先队列和最小优先队列。

一个最大优先队列支持以下4种操作：

• INSERT：将一个新结点插入堆中
• MAXIMUM：返回数组中的最大值
• EXTRACT_MAX：去掉并返回数组中的最大值
• INCREASE_KEY：将堆中的一个子结点的值增加到k

---

首先我们来实现MAXIMUM操作。实现这个操作只需要先对数组进行建堆，然后返回数组的第一个元素即可。

int maximum(int array[], int arraySize)
{
   
    buildMaxHeap(array, arraySize);

    return array[0];
}

然后实现EXTRACT_MAX操作：

int extract_max(int array[], int arraySize)
{
   
    buildMaxHeap(array, arraySize);

    int max = array[0];

    array[0] = array[arraySize - 1];
    maxHeapify(array, arraySize, 1);

    return max;
}

INCREASE_KEY操作的实现：当我们将堆中的某一个子结点的值增加到k时，如果它的值大于父结点的值，则将其与父结点交换。交换后以该结点为根结点的二叉树符合最大堆的性质。然后再将其与父结点比较。重复比较和交换的步骤直至整个二叉树都符合最大堆的性质。

void increaseKey(int heap[], int heapSize, int index, int key)
{
   
    if (heap[index - 1] > key)
    {
   
        printf("Error!\n");

        return;
    }

    heap[index - 1] = key;

    while (index > 1 && heap[PARENT(index) - 1] < heap[index - 1])
    {
   
        int temp = heap[PARENT(index) - 1];

        heap[PARENT(index) - 1] = heap[index - 1];
        heap[index - 1] = temp;
        index = PARENT(index);
    }

    return;
}

INSERT操作可以通过先向堆中追加一个无穷小值，然后将这个值增加到key，然后再调用increaseKey函数来实现。

#include <limits.h>

void insert(int array[] /* arraySize > heapSize */, int heapSize, int key)
{
   
    array[heapSize] = INT_MIN;
    increaseKey(array, heapSize + 1, heapSize + 1, key);

    return;
}