#include <bits/stdc++.h>
using namespace std;

//建立堆积树（从下往上调整）
void create_heap(vector<int> &a, int i, int heapsize)
{
    int largest = i;
    int temp = a[i];
    int left = 2 * i + 1;
    int right = left + 1;
    //判断当前节点和左右儿子的关系，并用largest记录值较大的结点编号
    if (left < heapsize && a[i] < a[left])
        largest = left;
    if(right < heapsize && a[largest] < a[right])
        largest = right;
    if(largest != i)
    {
        swap(a[i], a[largest]);//如果有儿子节点大于父节点则交换
        //避免交换后，largest这个节点和其儿子节点的结构发生混乱，不满足最大堆，所以递归调整
        create_heap(a, largest, heapsize);
    }
}

//堆排序
void heap_sort(vector<int> &a)
{
    int length = a.size();
    // 从最后一个非叶子节点向上建立最大堆
    for(int i = length/2 - 1; i >= 0; --i)
    {
        create_heap(a, i, length);
    }
    // 将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，
    // 再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。
    for(int i = length - 1; i >= 0; --i)
    {
        swap(a[i], a[0]);
        create_heap(a, 0, i);
    }
}

int main(int argc, char const *argv[])
{
    vector<int> vec1 = {7, 8, 9, 5, 3, 6, 1};
    heap_sort(vec1);
    for (const auto v : vec1)
        cout << v << " ";
    cout << endl;

    vector<int> vec2 = vec1;
    //STL中的建堆和堆排序
    make_heap(vec2.begin(), vec2.end());
    sort_heap(vec2.begin(), vec2.end());
    for (const auto v : vec2)
        cout << v << " ";
    cout << endl;
    system("pause");
    return 0;
}