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.
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)
- 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 = data, 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)