Heap Sort is a sorting algorithm based on the heap data structure. A heap is a tree based data structure where the tree is a complete binary tree. A complete binary tree is a binary tree in which all levels are completely filled, except the last level which may or may not be completely filled. Heaps can be of two types:

**Max Heap:**In max heap, every parent node must have value greater than or equal to it's child's value.**Min Heap:**In min heap, every parent node must have value less than it's child's value.

We are going to use the Max Heap for heap sort here. The sorting process includes: construction of a heap from the data, a max heap precisely, swapping of the first and last node, removing the last node from the heap and processing it for the remaining. With each cycle, the heap gets smaller and the list gets to sort.

### Illustration:

### Algorithm

```
1. Construct max heap from the list
2. Swap the first node with the last node
3. Remove last node from heap
4. Perform step 1 to 3 for the remaining heap
5. Stop when heap empty
```

```
heapSort(list)
n=length of list
for i from n//2-1 to -1 with inverval of -1
heapify(list,n,i)
for i from n-1 to 0 with interval -1
Swap valueAtIndex_i with valueAtIndex_0
heapify(list,i,0)
heapify(list,lengthofdata,i)
largest=i
leftchildIdx,l=2*i+1
rightchildIdx,r=2*i+2
if l<lengthofdata and valueAtlargest < valueAtl:
largest=l
if r<lengthofdata and valueAtlargest < valueAtr
largest=r
if largest!=i:
swap valueAti with valueAtlargest
perform recursion(heapify root), heapify(list,lengthofdata,largest)
```

**Time Complexity:**

- Worst Case:
**O(nlogn)** - Average Case:
**O(nlogn)** - Best Case:
**O(nlogn)**

**Space Complexity: O(1)**

### Program for Heap Sort:

```
def heapify(data, n, i):
largest = i
l = 2 * i + 1
r = 2 * i + 2
# Check if left child of root exists and is greater than root
if l < n and data[largest] < data[l]:
largest = l
# Check if right child of root exists and is greater than root
if r < n and data[largest] < data[r]:
largest = r
# If needed, Change the root
if largest != i:
data[i], data[largest] = data[largest], data[i] #Swap
heapify(data, n, largest) # Heapify Root.
def heapSort(data):
n = len(data)
# Building MaxHeap.
for i in range(n//2 - 1, -1, -1):
heapify(data, n, i)
# Extract elements one by one
for i in range(n-1, 0, -1):
data[i], data[0] = data[0], data[i] #Swap
heapify(data, i, 0)
inp=input("Enter the data: ").split()
data=[]
for i in inp:
data.append(int(i))
heapSort(data)
n = len(data)
print("Sorted List is")
print(data)
```