0% completed
Heaps are Unnecessary
fumingq
Aug 24, 2023
Since searching through a heap for the minimum is a O(k) operation, it's easer to just use a linked list and just insertion sort, which is what python's built in list is supposed to be. In fact, if you wanted to implement a binary search for insert and removal, then it would be O(log k) for each update operation leading to an overall time of O(n log k) which is faster than the given solution.
1
0
Comments
Design Gurus2 years ago
Did you try implementing this approach? Can you please share your solution code?
Lee 2 years ago
How would you binary search a linked list? It's not an array, so you don't get O(1) access to list elements. If you used a linked list, then the best you can do for finding the insert location is O(k). If you use an array, sure you can find the insert location in O(log ...
On this page