Heap Sort

Heapsort is an efficient sorting algorithm that is used to sort a collection of elements in a particular order. It is a comparison-based sorting algorithm, which means that it compares elements to each other and sorts them according to the comparison results. Heapsort is one of the most commonly used sorting algorithms and is the basis of many other sorting algorithms. Heapsort is a popular algorithm used in many programming languages and is included in the Data Structures and Algorithms with Python course. In this article, we will discuss how Heapsort works, the time complexity of Heapsort (best, average, and worst), and the space complexity of Heapsort (worst). We will also include Python code to teach each topic.

What is Heapsort?

Heapsort is an efficient sorting algorithm that is used to sort a collection of elements in a particular order. It is a comparison-based sorting algorithm, which means that it compares elements to each other and sorts them according to the comparison results. Heapsort is a popular algorithm used in many programming languages and is included in the Data Structures and Algorithms with Python course. Heapsort is based on a data structure called a binary heap. A binary heap is a complete binary tree which satisfies the heap property. The heap property states that the value of any node in the binary tree is less than or equal to its child nodes. The binary tree is then used to build a heap which is used by Heapsort to sort the elements.

How Heapsort Works

Heapsort works by first creating a binary heap from the collection of elements. The binary heap is then used to build a heap which is used by Heapsort to sort the elements. The Heapsort algorithm consists of two steps. The first step is to build the binary heap which is done by comparing each node to its children and swapping them if the parent node is larger than the child node. The second step is to sort the elements. This is done by removing the root node of the binary heap and placing it in the sorted array. The remaining elements are then reheapified and the process is repeated until all elements have been placed in the sorted array.

Time Complexity (Best, Average, and Worst)

The time complexity of Heapsort depends on the size of the input array. The best case time complexity of Heapsort is O(n log n), which is when the array is already sorted. The average case time complexity of Heapsort is also O(n log n) and the worst case time complexity is O(n log n).

Space Complexity (Worst)

The space complexity of Heapsort is O(1), which means that it does not require additional memory to perform the sorting operation.

Python Code

The following code shows how to implement Heapsort in Python.

# Function to build the binary heap 
def build_heap(arr): 
 
	n = len(arr) 
	# Build a max heap 
	for i in range(n, -1, -1): 
		heapify(arr, n, i) 
	
# Heapify function 
def heapify(arr, n, i): 
	largest = i # Initialize largest as root 
	l = 2 * i + 1	 # left = 2*i + 1 
	r = 2 * i + 2	 # right = 2*i + 2 
	
	# See if left child of root exists and is 
	# greater than root 
	if l < n and arr[i] < arr[l]: 
		largest = l 
	
	# See if right child of root exists and is 
	# greater than root 
	if r < n and arr[largest] < arr[r]: 
		largest = r 
	
	# Change root, if needed 
	if largest != i: 
		arr[i],arr[largest] = arr[largest],arr[i] # swap 

		# Heapify the root. 
		heapify(arr, n, largest) 

# The main function to sort an array of given size 
def heapsort(arr): 
	n = len(arr) 
	
	# Build a maxheap. 
	build_heap(arr) 
	
	# One by one extract elements 
	for i in range(n-1, 0, -1): 
		arr[i], arr[0] = arr[0], arr[i] # swap 
		heapify(arr, i, 0) 

# Driver code to test above 
arr = [ 12, 11, 13, 5, 6, 7] 
heapsort(arr) 
n = len(arr) 
print ("Sorted array is") 
for i in range(n): 
	print ("%d" %arr[i]), 

Conclusion

Heapsort is an efficient sorting algorithm that is used to sort a collection of elements in a particular order. It is a comparison-based sorting algorithm, which means that it compares elements to each other and sorts them according to the comparison results. Heapsort is a popular algorithm used in many programming languages and is included in the Data Structures and Algorithms with Python course. Heapsort works by first creating a binary heap from the collection of elements. The binary heap is then used to build a heap which is used by Heapsort to sort the elements. The time complexity of Heapsort depends on the size of the input array and is best, average, and worst case time complexity is O(n log n). The space complexity of Heapsort is O(1), which means that it does not require additional memory to perform the sorting operation.

Exercises

def heapsort(arr): 
	n = len(arr) 
	
	# Build a maxheap. 
	build_heap(arr) 
	
	# One by one extract elements 
	for i in range(n-1, 0, -1): 
		arr[i], arr[0] = arr[0], arr[i] # swap 
		heapify(arr, i, 0) 
	
	return arr

# Function to build the binary heap 
def build_heap(arr): 
 
	n = len(arr) 
	# Build a max heap 
	for i in range(n, -1, -1): 
		heapify(arr, n, i) 
	
# Heapify function 
def heapify(arr, n, i): 
	largest = i # Initialize largest as root 
	l = 2 * i + 1	 # left = 2*i + 1 
	r = 2 * i + 2	 # right = 2*i + 2 
	
	# See if left child of root exists and is 
	# greater than root 
	if l < n and arr[i] < arr[l]: 
		largest = l 
	
	# See if right child of root exists and is 
	# greater than root 
	if r < n and arr[largest] < arr[r]: 
		largest = r 
	
	# Change root, if needed 
	if largest != i: 
		arr[i],arr[largest] = arr[largest],arr[i] # swap 

		# Heapify the root. 
		heapify(arr, n, largest) 

# The main function to sort an array of given size 
def heapsort(arr): 
	n = len(arr) 
	
	# Build a maxheap. 
	build_heap(arr) 
	
	# One by one extract elements 
	for i in range(n-1, 0, -1): 
		arr[i], arr[0] = arr[0], arr[i] # swap 
		heapify(arr, i, 0) 

# Driver code to test above 
arr = [ 12, 11, 13, 5, 6, 7] 
heapsort(arr) 
n = len(arr) 
print ("Sorted array is") 
for i in range(n): 
	print ("%d" %arr[i]),