Heap as a tree:
An array can be visualized as a nearly complete binary tree.

Properties of this tree:
- Root of the tree : First element of the array
- Parent of element at index i : element at index i/2
- left child of element at index i : element at index 2*i
- Right child of element at index i : element at index 2*i+1
Max heap:
In max heap, the parent's value is higher than both of its children.
Heap Operations:
- Build_max_heap: Produces a max heap from an unordered array
- max_heapify: Correct a single violation of the heap property in a subtree's root
Heap Sort algorithm steps:
- Build max-heap from unordered array
- Find max element in Array A, A[n]
- Swap this element A[n] from A[1], now max element is at the end of array
- Now discard the node 'n' from the heap by decrementing heap size
- New root may violate the max heap property, but children are max heaps, so run max heapify to fix
Heap Sort Pseudocode Implementation in Java:
public class HeapSort {
private static int N;
public static void sort(int arr[]){
heapify(arr);
for (int i = N; i > 0; i--){
swap(arr,0, i);
N = N-1;
maxheap(arr, 0);
}
}
public static void heapify(int arr[]){
N = arr.length-1;
for (int i = N/2; i >= 0; i--)
maxheap(arr, i);
}
public static void maxheap(int arr[], int i){
int left = 2*i ;
int right = 2*i + 1;
int max = i;
if (left <= N && arr[left] > arr[i])
max = left;
if (right <= N && arr[right] > arr[max])
max = right;
if (max != i){
swap(arr, i, max);
maxheap(arr, max);
}
}
public static void swap(int arr[], int i, int j){
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
public static void main(String[] args){
int n, i;
System.out.println("Enter number of integer elements");
n = 10;
int arr[] = {16, 14, 10, 8, 7, 9, 3, 2, 4, 1};
System.out.println("\nElements before sorting ");
for (i = 0; i < n; i++)
System.out.print(arr[i]+" ");
System.out.println();
sort(arr);
System.out.println("\nElements after sorting ");
for (i = 0; i < n; i++)
System.out.print(arr[i]+" ");
System.out.println();
}
}
Output:
Heap Sort Algorithm Time Complexity:
- Build_max_heap takes O(logn) time
- Swapping elements in the array takes O(1) time, but running it for n elements makes it O(n)
- We're building max_heap for every element, so its time complexity becomes O(nlogn)