heap_sort.cpp

// Sắp xếp lại cây, sao cho phần tử cha luôn lớn hơn phần tử con của nó
void Heapify(int *a, int N, int i)
{
    int Left = 2*i + 1, Right = 2*i + 2, Largest;

    if(Left < N && a[Left] > a[i]) Largest = Left;
    else Largest = i;
 
    if(Right < N && a[Right] > a[Largest]) Largest = Right;
 
    if(Largest != i)
    {
        swap(a[i], a[Largest]);
        Heapify(a, N, Largest);
    }
}
     
// Xây dựng mô hình cây nhị phân sao cho phần tử cha luôn lớn hơn phần tử con
void BuildHeap(int *a, int N)
{
    for(int i = N/2-1; i >= 0; i--)
        Heapify(a, N, i);
}
     
// Hàm chính
void Heap(int *a, int N)
{
    BuildHeap(a, N);
     
    for(int i = N - 1; i >= 0; i--)
    {
        // cho phần tử lớn nhất xuống dưới cùng,
        // sau đó, cập nhật lại cây
        swap(a[i], a[0]);
        Heapify(a, i, 0);
    }
}