Given an array of integers arr
, sort the array using a Heap. This is called "Heap Sort".
The idea is to turn your original Array into a Heap using "heapify", which takes O(n) time.
You can then repeatedly pop the smallest value from the Heap, and transfer it over to a new Array. The new Array will end up sorted when you're done.
Time Complexity O(nlogn)
We first use heapify which takes O(n). We then pop the heap n times, and popping takes O(logn) each time, since the heap has O(n) elements in it. This takes O(n)+O(nlogn)=O(nlogn) time.
Space Complexity O(1)
We're just transferring elements from the Heap to the sorted array. As the sorted array grows, the Heap shrinks. This means the space complexity is O(1) - there's no extra space needed.
TreeNode.of
function can be used to create an entire binary tree using 1 line of code. The input is a BFS traversal of the tree including nulls, and the output is the root node of the tree.TreeNode.of([1, None, 2, None, 3])
ListNode.of
function lets you create an entire Linked List using 1 line of code. The input is an array, and the output is the head of the Linked List.ListNode.of([1, 2, 3])
ListNode.of([1, 2, 3], 1)
GraphNode.of
function lets you create an entire Graph using 1 line of code. The input is an Adjacency Matrix, and the output is the first node in the matrix.GraphNode.of([ ['A', 1, 2], ['B', 2], ['C', 0] ])
[['__init__', 15], ['add', 16], ['get']]
c = MyClass(15) c.add(16) c.get()
TreeNode.of
function can be used to create an entire binary tree using 1 line of code. The input is a BFS traversal of the tree including nulls, and the output is the root node of the tree.TreeNode.of([1, None, 2, None, 3])
ListNode.of
function lets you create an entire Linked List using 1 line of code. The input is an array, and the output is the head of the Linked List.ListNode.of([1, 2, 3])
ListNode.of([1, 2, 3], 1)
GraphNode.of
function lets you create an entire Graph using 1 line of code. The input is an Adjacency Matrix, and the output is the first node in the matrix.GraphNode.of([ ['A', 1, 2], ['B', 2], ['C', 0] ])
[['__init__', 15], ['add', 16], ['get']]
c = MyClass(15) c.add(16) c.get()