If I have a list and need to sort it, is there a good reason to use list.sort() over heapq.heapify(list), given that heapify is O(N) (link) and .sort() is O(NlogN)?

Why isn't the default sort algorithm heapify if heapify is faster?

CodePudding user response：

as guys have said in the comment section, "heapify" rearranges elements of the list to form a heap-oriented binary tree.

bad sorting is usually done using O(n * n) so having O(n * logn) makes it way faster. most of the good sorting libraries do sorting in n * logn time.

you can use heaps to sort your array in n*logn time like:

import heapq

a = [3, 6, 1, 3, 7, 9]
    
def sort_with_heap(a):
    """
    sort O(nlogn)
    """
    heapq.heapify(a) # heapify's the list O(n)

    while len(a) > 0: # O(n) times
        yield heapq.heappop(a) # O(logn)


print(list(sort_with_heap(a)))
>> [1, 3, 3, 6, 7, 9]

note: that the example above is for the sake of understanding how heaps can be used for sorting and is not space optimal. to do proper sorting using heaps take a look at heapsort (which works with max-oriented heaps) and doesn't use any additional space than the sorting array itself. i've wrote one myself in here.