# 1. Introduction

*Heap Sort* is a comparison-based sorting technique based on the Binary Heap data structure. It divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element and moving that to the sorted region.

# 2. Program Steps

1. Build a max heap from the input data.

2. At this point, the largest item is stored at the root of the heap. Replace it with the last item of the heap followed by reducing the size of the heap by one. Finally, heapify the root of the tree.

3. Repeat step 2 while the size of the heap is greater than 1.

# 3. Code Program

```
public class HeapSort {
// Main function to do heap sort
public static void sort(int arr[]) {
int n = arr.length;
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// One by one extract an element from heap
for (int i = n - 1; i >= 0; i--) {
// Move current root to end
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// Call max heapify on the reduced heap
heapify(arr, i, 0);
}
}
// To heapify a subtree rooted with node i which is an index in arr[]
static void heapify(int arr[], int n, int i) {
int largest = i; // Initialize largest as root
int l = 2 * i + 1; // left = 2*i + 1
int r = 2 * i + 2; // right = 2*i + 2
// If left child is larger than root
if (l < n && arr[l] > arr[largest])
largest = l;
// If right child is larger than the largest so far
if (r < n && arr[r] > arr[largest])
largest = r;
// If largest is not root
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
// Recursively heapify the affected sub-tree
heapify(arr, n, largest);
}
}
// Driver method
public static void main(String[] args) {
int arr[] = {12, 11, 13, 5, 6, 7};
// Call sort method to sort the array
sort(arr);
// Print the sorted array
System.out.println("Sorted array:");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
}
```

### Output:

Sorted array: 5 6 7 11 12 13

# 4. Step By Step Explanation

1. The *heapify* function is used to maintain the heap property. It ensures that the subtree rooted at a given index is a max-heap. If the heap property is violated, it recursively fixes the property by propagating the largest element up.

2. The primary logic of the heap sort resides in the *sort* function. It first builds a max-heap, ensuring that the largest element is at the root.

3. Once the max-heap is built, the root element (the largest element) is swapped with the last element in the array, reducing the heap size by 1. The root element is then heapified to maintain the max-heap property.

4. This process continues, extracting the maximum element from the heap and placing it at the end of the sorted section of the array until the entire array is sorted.

*Heap Sort* is an in-place sorting algorithm with a time complexity of O(n log n) for the worst, average, and best cases.