堆的结构实现与堆排序

1. 堆

堆是特殊的完全二叉树的情况，因此我们来大致来了解一下完全二叉树：

简单来说，完全二叉从上至下，从左往右进行编号，总会有连续（不间断）的1 ~ n序号。

堆在二叉树的基础上，满足：任意结点小于（大于）它的所有子结点，最小（大）值的结点位于根结点。如果根结点为最大值的结点则为最大堆，值大于它的所有子结点；相反，则为最小堆，如下图所示：

2. 堆的实现

底层结构

我们可以对堆的每个结点从上至下，从左往右进行编号，并将每个结点的序号按照下标将值存储到数组当中。因此，我们可以用一个数组来实现堆的数据结构。如下图所示：

进行这样的抽象后，可以很方便获取到某结点的父结点与左右结点的序号，它们满足（假设某结点序号为i）：

• 父结点： (i - 1) / 2

• 左结点：2 * i + 1；右结点：2 * i + 2

构造堆

对于给定一个乱序的完全二叉树数组，我们需要调整为正常的堆结构。首先需要了解的一步操作是heapify。例如对于给定的二叉树：

从根结点进行调整（针对最大堆），因为左结点10大于根结点，所以将它们交换位置；交换之后其左结点5仍然大于4，继续交换它们的位置，直到左右节点为空。调整完成的结果如下：

代码实现为：

public void heapify(int[] tree, int n, int i) {
    if (i >= n) return; // 递归出口，序号大于n说明结点为空

    int left = 2 * i + 1, right = 2 * i + 2;
    int max = i;  // 找到父节点、左结点、右结点较大的那个数的序号
    
    if (left < n && tree[left] > tree[max]) {
        max = left;
    }
    if (right < n && tree[right] > tree[max]) {
        max = right;
    }
    if (max != i) { // 父结点不是最大时进行调整
        swap(tree, max, i);     // 交换结点的值
        heapify(tree, n, max);  // 递归进行调整
    }
}

public void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

可以发现，上列的完全二叉树右子树是完整的堆结构。如果所给的二叉树左右子树都需要进行调整，则单单一个heapify则不够：

我们可以**从最后一个结点的父结点序号开始往上调整。对于上图来说，我们从尾结点9的父节点2开始调用heapify进行调整即可：

public void buildHeap(int[] tree, int n) {
    int last = n - 1;             // 最后一个结点
    int parent = (last - 1) / 2;  // 最后一个结点的父结点

    for (int i = parent; i >= 0; i--) {  // 从parent序号的结点开始倒着调用heapify
        heapify(tree, n, i);
    }
}

交换的过程如下：

3. 堆排序

对于一个给定的乱序数组，我们将该数组看成是乱序的完全二叉树结构。首先调用buildHeap进行构造调整为正常的堆结构。

然后每次将根结点与末尾序号的节点（尾结点）进行交换，并切割掉该尾结点，再调用heapify重新调整为正常的堆结构，重复该操作直至堆的结构为空。我们可以用一个for循环来完成并省去切割尾结点的操作。变量i代表当前堆的尾结点序号：

public void heapSort(int[] tree, int n) {
    buildHeap(tree, n);
    for (int i = n - 1; i >= 0; i--) {
        swap(tree, i, 0);     // 根结点与最后一个结点进行交换
        heapify(tree, i, 0);  // i代表当前剩余的结点数量，指向堆的尾结点
    }
}

可以发现，每次切割出来的尾结点（最大的元素）将会被追加到数组的末尾（每次都进行了交换），当循环结束时，原先的乱序数组将会升序排列。

---