Pre-requisite: What is Heap Sort?
Heapsort is a comparison-based sorting technique based on a Binary Heap data structure. It is similar to selection sort where we first find the maximum element and place the maximum element at the end. We repeat the same process for the remaining element.
Python Program for Heap Sort
The given Python code implements the Heap Sort algorithm, which is an efficient comparison-based sorting method. Heap Sort works by building a binary heap and repeatedly extracting the maximum element (in the case of a max heap) from the heap, which is then placed at the end of the sorted portion of the array. The code comprises three main functions: heapify, heapSort, and the driver code.
The heapify function is responsible for maintaining the heap property of the binary tree. Given an array, the function adjusts the element at index i such that the subtree rooted at index i satisfies the heap property, i.e., the parent is greater than its child nodes.
The heapSort function orchestrates the sorting process. It first converts the input array into a max heap by using the heapify function iteratively. Once the max heap is constructed, the function swaps the root (largest element) with the last element and re-heapifies the reduced heap. This process is repeated until the entire array is sorted.
The driver code initializes an array, applies the heapSort function to sort it, and then prints the sorted array. The array [12, 11, 13, 5, 6, 7] is used as an example. After sorting, the output displays the elements in ascending order.
In summary, the code demonstrates the implementation of Heap Sort, which efficiently sorts an array by creating a max heap and repeatedly extracting the maximum element from it. Heap Sort’s time complexity is O(n log n), making it suitable for large datasets.
Python
#!/usr/bin/python# -*- coding: utf-8 -*-# Python program for implementation of heap Sort# To heapify subtree rooted at index i.# n is size of heapdef 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 sizedef heapSort(arr): n = len(arr) # Build a maxheap. # Since last parent will be at ((n//2)-1) we can start at that location. for i in range(n // 2 - 1, -1, -1): heapify(arr, n, i) # 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 abovearr = [12, 11, 13, 5, 6, 7, ]heapSort(arr)n = len(arr)print('Sorted array is')for i in range(n): print(arr[i])# This code is contributed by Mohit Kumra |
Sorted array is 5 6 7 11 12 13
Time Complexity: O(n*log(n))
- The time complexity of heapify is O(log(n)).
- Time complexity of createAndBuildHeap() is O(n).
- And, hence the overall time complexity of Heap Sort is O(n*log(n)).
Auxiliary Space: O(log(n))
Heap Sort using Python STL
Steps:
- Import the Python STL library “heapq“.
- Convert the input list into a heap using the “heapify” function from heapq.
- Create an empty list “result” to store the sorted elements.
- Iterate over the heap and extract the minimum element using “heappop” function from heapq and append it to the “result” list.
- Return the “result” list as the sorted output.
Python3
import heapq# Function to perform the sorting using# heaop sortdef heap_sort(arr): heapq.heapify(arr) result = [] while arr: result.append(heapq.heappop(arr)) return result # Driver Codearr = [60, 20, 40, 70, 30, 10]print("Input Array: ", arr)print("Sorted Array: ", heap_sort(arr)) |
Input Array: [60, 20, 40, 70, 30, 10] Sorted Array: [10, 20, 30, 40, 60, 70]
Time Complexity: O(n log n), where “n” is the size of the input list.
Auxiliary Space: O(1).
Please refer complete article on Heap Sort for more details!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!