HeapSort: The simplest sorting algorithm.

Question

Sort an array using heaps

Example 1:

Input: nums = [5,2,3,1]
Output: [1,2,3,5]

Example 2:

Input: nums = [5,1,1,2,0,0]
Output: [0,0,1,1,2,5]

Leetcode (Sort an Array)

Implementation

1. Create a minheap
1. We can use heapify in Python to create a heap in O(N) time complexity.
2. Sort the array
1. To sort the array using HeapSort, we simply need to call the heappop operation n times and add the poped item to an array. The pop operation has a time complexity of O(log N), leading to a total time complexity of nlogn.
3. That's it! The simplest sorting algorithm.
Copy

import heapq
class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:

        heapify(nums)
        merged = []
        for i in range(len(nums)):
            merged.append(heappop(nums))
        return merged

Time complexities

Time O(n*log(n))

Space O(n)