Can you explain the working principle of heap sort and how it organizes the data sorting process?

Heap Sort is a sorting algorithm based on the data structure "heap," typically a binary heap.

Working principle:

1. Building the heap: The initial array is transformed into a max heap — a binary tree where each parent node is greater than or equal to its children.
2. Extracting the maximum: The root of the heap (the maximum element) is swapped with the last element of the array, and the size of the heap is reduced by 1.
3. Heap restoration: After the swap, the heap property is restored for the remaining part of the array.
4. Repeating: Steps 2-3 are repeated until the heap size reduces to 1.

As a result, the array is sorted in ascending order.

Example in C++ (simplified):

void heapify(int arr[], int n, int i) {
    int largest = i;
    int left = 2*i + 1;
    int right = 2*i + 2;

    if (left < n && arr[left] > arr[largest])
        largest = left;
    if (right < n && arr[right] > arr[largest])
        largest = right;

    if (largest != i) {
        std::swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

void heapSort(int arr[], int n) {
    // Building the heap
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    // Extracting elements from the heap
    for (int i = n - 1; i >= 0; i--) {
        std::swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

Thus, heap sort efficiently orders data in O(n log n) time without additional memory.