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)) |
Output
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!
Python Program for Heap Sort
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.