heapsort coding for python 3

Question

def heapSort(lst):

    heap = arrayHeap.mkHeap(len(lst), arrayHeap.less)
    alst = list(lst)
    while alst != []:
        v = alst.pop(0)
        arrayHeap.add (heap, v)

    while heap.size != 0:
        w = arrayHeap.removeMin(heap)
        alst.append(w)
    return last

is this a valid heap sort function?

Answer 1

Assuming your arrayHeap provides the same guarantees as the stdlib's heapq or any other reasonable heap implementation, then this is a valid heap sort, but it's a very silly one.

By copying the original sequence into a list and then popping from the left side, you're doing O(N^2) preparation for your O(N log N) sort.

If you change this to pop from the right side, then you're only doing O(N) preparation, so the whole thing takes O(N log N), as a heapsort should.

That being said, I can't understand why you want to pop off the list instead of just iterating over it. Or, for that matter, why you want to copy the original sequence into a list instead of just iterating over it directly. If you do that, it will be faster, and use only half the memory, and be much simpler code. Like this:

def heapSort(lst):
    heap = arrayHeap.mkHeap(len(lst), arrayHeap.less)
    for v in lst:
        arrayHeap.add(heap, v)
    alst = []
    while heap.size:
        w = arrayHeap.removeMin(heap)
        alst.append(w)
    return last

With a slightly nicer API, like the one in the stdlib's heapq module (is there a reason you're not using it, by the way?), you can make this even simpler:

def heapSort(lst):
    alst = []
    for v in lst:
        heapq.heappush(alst, v)
    return [heapq.heappop(alst) for i in range(len(alst))]

… or, if you're sure lst is a list and you don't mind mutating it:

def heapSort(lst):
    heapq.heapify(lst)
    return [heapq.heappop(lst) for i in range(len(lst))]

… or, of course, you can copy lst and then mutate the copy:

def heapSort(lst):
    alst = lst[:]
    heapq.heapify(alst)
    return [heapq.heappop(alst) for i in range(len(alst))]

You may notice that the first one is the first of the Basic Examples in the heapq docs.