Heap 数据结构一般都被看做是一棵完全二叉树对象，我们知道对于完全二叉树可以使用连续的数组空间来存储各个结点关系。 Heap 是一种非常重要的数据结构，使用 Heap 可以实现高效的排序、构建优先级队列等等。Heap 主要分为两种：

1. 如果完全二叉树中的每棵子树的根节点都大于左右子树结点，叫做大顶堆
2. 如果完全二叉树中的每棵子树的根节点都小于左右子树结点，叫做小顶堆

左图为大顶堆，右图为数组。我们可以将完全二叉树存储到右侧的数组中。

1. 如果定义第一个结点的下标为 1 的话，那么左节点为 2*i，右结点为 2*i+1
2. 如果定义第一个结点的下标为 0 的话，那么左节点为 2*i+1，右节点为 2*i+2

对于大顶堆而言, 数组的下标为 1 的元素肯定是整个数组中最大的元素，对于小顶堆则是最小的元素。

1. 初始化和调整堆算法

max_heapify 函数是堆的构造和调整过程中最重要的函数，它用于保持堆的性质。该函数的思路如下：

1. vec 表示进行排序的 vector 容器对象
2. non_leaf_index 表示要调整的非叶子结点索引
3. element_number 表示要调整的元素数量，例如：有 100 个元素，已经使得 2 个元素有序了，那么需要调整的元素就只有 98 个
4. 第 35-42 行代码表示当我们交换了某个值时，很有可能导致不满足堆的性质，所以需要递归向下再去调整堆，使其满足堆的性质。

/*
 * @param non_leaf_index 表示要调整的非叶子结点索引
 * @param element_number 表示要调整的元素数量
 * @return NULL
 * 调整指定的非叶子结点使得满足堆特性
 * */
void max_heapify(vector<int>& vec, int non_leaf_index, int element_number)
{
    // 如果当前结点为叶子结点, 则终止函数
    if (non_leaf_index >= element_number / 2)
    {
        return;
    }

    // 获得当前结点左右结点索引
    int lchild_index = 2 * non_leaf_index + 1;
    int rchild_index = 2 * non_leaf_index + 2;

    // 最大元素的索引
    int max_index = non_leaf_index;

    // 判断左节点是否比当前父节点节点大
    if (lchild_index <= element_number && vec[lchild_index] > vec[max_index])
    {
        max_index = lchild_index;
    }

    // 判断左节点是否比当前父节点大
    if (rchild_index < element_number && vec[rchild_index] > vec[max_index])
    {
        max_index = rchild_index;
    }

    // 最大值交换到当前父节点
    if (max_index != non_leaf_index)
    {
        // 将最大值交换到当前非叶子结点索引
        swap(vec[max_index], vec[non_leaf_index]);
        // 由于交换之后可能导致不满足堆特性, 需要递归向下调整
        // max_index 代表被交换的左节点索引、或者右结点索引
        max_heapify(vec, max_index, element_number);
    }
}

2. 堆排序算法的实现

堆排序算法的思路主要：

1. 自顶向上初始化堆
2. 交换头尾两个元素
3. 自上向下调整堆
4. 重复上述步骤，直到序列有序

void heap_sort(vector<int>& vec)
{
    // 获得数组元素个数
    int element_number = vec.size();

    // 自底向上初始化堆
    for (int non_leaf_index = element_number / 2 - 1; non_leaf_index >= 0; --non_leaf_index)
    {
        max_heapify(vec, non_leaf_index, element_number);
    }

    // 自上而下调整堆
    for (int i=element_number-1; i>=0; --i)
    {
        // 交换头尾两个元素
        swap(vec[0], vec[i]);
        // 调整堆使其满足堆特性
        max_heapify(vec, 0, i);
    }
}

测试代码如下：

int main()
{
    // 初始化数组
    vector<int> vec;
    for (int i = 0; i < 10; ++i)
    {
        vec.push_back(rand() % 100 + 1);
    }

    // 打印数组元素
    print_vector(vec, "排序前:");
    heap_sort(vec);
    print_vector(vec, "排序后:");

    // 判断序列是否有序
    if (is_sorted(vec.begin(), vec.end()))
    {
        printf("数组有序");
    }
    else
    {
        printf("数组无序");
    }

    return 0;
}

程序输出结果：

排序前:
-------------------
8 50 74 59 31 73 45 79 24 10 
-------------------
排序后:
-------------------
8 10 24 31 45 50 59 73 74 79 
-------------------
数组有序