数据结构与算法-算法篇：排序—堆排序（七）

数据结构与算法系列文章：数据结构与算法目录

堆排序，是利用堆这种数据结构，将排序数组看成是一棵完全二叉树的顺序存储结构，来进行排序的算法。

解释一下堆和二叉树：

堆：

堆(heap)又被为优先队列。尽管名为优先队列，但堆并不是队列。
因为队列中允许的操作是先进先出（FIFO），在队尾插入元素，在队头取出元素。
而堆虽然在堆底插入元素，在堆顶取出元素，但是堆中元素的排列不是按照到来的先后顺序，而是按照一定的优先顺序排列的。

堆的一个经典的实现是完全二叉树，这样实现的堆称为二叉堆。

满二叉树与完全二叉树：

满二叉树：除了叶子节点，所有的节点的左右孩子都不为空，就是一棵满二叉树，如下图：

满二叉树.png

可以看出：满二叉树所有的节点都拥有左孩子，又拥有右孩子。

完全二叉树：不一定是一个满二叉树，但它不满的那部分一定在右下侧，如下图：

完全二叉树.png

堆的特性：

1、必须是完全二叉树；
2、任一结点的值是其子树所有结点的最大值或最小值；

最大值时，称为“最大堆”，也称大顶堆；
最小值时，称为“最小堆”，也称小顶堆，如下图：

最大堆、最小堆.png

堆排序基本思想：

1.将要排序的数组创建为一个大根堆。大根堆的堆顶元素就是这个堆中最大的元素。
2.将大根堆的堆顶元素和无序区最后一个元素交换，并将无序区最后一个位置例入有序区，然后将新的无序区调整为大根堆。
重复操作，无序区在递减，有序区在递增。
初始时，整个数组为无序区，第一次交换后无序区减一，有序区增一。
每一次交换，都是大根堆的堆顶元素插入有序区，所以有序区保持是有序的。

堆与数组的关系：

堆是一种逻辑结构（形象的表示数据的存储格式），数组则是数据的实际存储结构（对应数据的存储地址），堆中的根节点与左右子节点在存储数组中的位置关系如下：假设根节点在数组中的位置（数组下标）为 i ，那么左节点在数组中的位置（数组下标）为 i * 2 + 1 ，右节点在数组中的位置（数组下标）为 i * 2 + 2 。

实现：

/// <summary>
/// 堆排序算法
/// </summary>
/// <param name="arr"></param>
public void HeapSort(int[] arr)
{
    // 构建大顶堆（初始状态看出：整体无序）
    BuildMaxHeap(arr);

    for (int i = arr.Length - 1; i > 0; i--)
    {
        // 将堆顶元素依次与无序区的最后一位交换（取出堆顶元素进入有序区）
        Swap(arr, 0, i);
        // 重新将无序区调整为大顶堆
        MaxHeapify(arr, 0, i);
    }
}

/// <summary>
/// 构建大顶堆（根节点大于左右节点）
/// </summary>
/// <param name="arr"></param>
private void BuildMaxHeap(int[] arr)
{
    // 根据大顶堆的性质可知：数组的前半段的元素为根节点，其余都为叶节点

    // 遍历调整：从最底层的最后一个根节点开始进行大顶堆调整
    for (int i = arr.Length / 2; i >= 0; i--)
    {
        // 调整大顶堆
        MaxHeapify(arr, i, arr.Length);
    }
}

/// <summary>
/// 大顶堆调整过程
/// </summary>
/// <param name="arr">待调整的数组</param>
/// <param name="currentIndex">待调整元素在数组中的位置</param>
/// <param name="length">堆中所有元素个数</param>
private void MaxHeapify(int[] arr, int currentIndex, int length)
{
    // 左子节点在数组中位置
    int leftChild = 2 * currentIndex + 1;
    // 右子节点在数组中位置
    int rightChild = 2 * currentIndex + 2;
    // 记录此根节点、左子节点、右子节点，三者中最大值的位置
    int large = currentIndex;

    // 与左子节点进行比较
    if (leftChild < length && arr[leftChild] > arr[large])
    {
        large = leftChild;
    }
    // 与右子节点进行比较
    if (rightChild < length && arr[rightChild] > arr[large])
    {
        large = rightChild;
    }

    if (currentIndex != large)
    {
        // large发生变化：左右节点中有大于跟节点的情况

        // 将左右节点中的大者，与根节点进行交换，即：实现局部大顶堆
        Swap(arr, currentIndex, large);

        // 以上次调整动作的large位置（为此次调整的根节点位置），对整个进行递归调整
        MaxHeapify(arr, large, length);
    }
    else
    {
        // large没有变化，不需要调整
    }
}

/// <summary>
/// 交换数组的两个元素
/// </summary>
/// <param name="arr"></param>
/// <param name="i"></param>
/// <param name="j"></param>
private void Swap(int[] arr, int i, int j)
{
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}