Heap Sort in Python

This sorts the list in reverse, but that's still sorting, no issue there. But I think that should be noted in the code, since it is important and may not be expected. There are plenty of comments that explain the minutia, but not bigger things such as that. There is also no mention of what algorithm max_heap uses.

The way max_heap works is, to me, very confusing. At the face of it, it is not at all obvious what kind of iteration is happening here. The way the algorithm picks up where it left off after bubbling-up an item is remeniscent of Gnome sort, slowly walking over all the items in between again. That's clever, but a more conventional setup with a nice counted for-loop and a while-loop inside of it to bubble-up an item would not need to make repeated passes over the entire list.

So unless I made a mistake in my reasoning, and that is easily possible because this is a quite confusing arrangement, max_heap may take quadratic time in the worst case. That is not good, it can be done in linear time using the classic bottom-up heap construction, or at least in O(n log n) time using two loops, one over all the items and an other to bubble-up that item. O(n log n) construction isn't too bad, that is the overall complexity of HeapSort anyway, but O(n²) heap construction is a waste of a good algorithm. But maybe I'm wrong and maybe your algorithm isn't quadratic time, let me know, and add comments explaining the bigger picture.

The way max_heap is used is an other issue. First, sort_heap throws away a useful property of Heap Sort: it can be done in-place. That is done by extracting an item from the heap, which "shrinks" the heap by one place, then the extracted item goes into the space that was emptied at the end of the heap. That way, the sorted array is built up from the end, at the same time that the heap is being used up. It's a nice trick. Using it is not mandatory of course. This trick is why a max heap is usually used rather than a min heap: the biggest item is needed first, to put it at the end of the array.

A bigger issue is that max_heap keeps being used every time an item is removed from the heap. It's a very expensive way to restore the heap property, and there is a much better solution: grab the last item in the heap, make it the new root, then restore the heap property top-down (aka "bubble down"). That way only O(log n) work is involved per iterating of the sorting loop, instead of however much max_heap costs (which depends on the algorithm used, but at least linear time).

Due to this and the quadratic time max_heap (overall leading a cubic time algorithm), I would say that this algorithm does not match what Heap Sort is supposed to be.

I have improved my code and here's my new code:

 def max_heap(listmax):

    i = 1
    k = 0

    while i <= len(listmax) -1:

        if i%2 == 0:
            j = int(i/2 -1)
        else:
            j = int(i//2)

#   parent is compared with the child and swapped if not in order. 

        if listmax[i] > listmax[j]:
            listmax[i],listmax[j] = listmax[j],listmax[i]

#   k is used here to store the index of the latest node which is compared in the array. So that next time
#   the parent is compared to the child, then it starts with k+1 occurence.
#   coming inside this if loop means child was greater than parent and hence it was swapped. Also k will
#   now hold the index of child node

#   k is checked for 0 first because, we want to have the very first node when the swapping starts, so that 
#   the next node read should be from k+1 node

            if k == 0:
                k = i

#   i > 2 means that the child also becomes parent in the flow, so the child is made parent and checked in while loop            

            if i > 2: 
                if i%2 == 0:
                    i = int(i/2 -1)
                else:
                    i = int(i//2)
            else:
                if k > 2:
                    i = k +1
                else:
                    i = i +1
                k = 0
        else:

#   this else means, parent was greater than the child, so no swapping happened
#   k has the value of last child where the swapping started so next node to be read should be k+1
#   if k is zero, it means the last child which was read was already smaller than parent and hence we 
#   just move to next node by i +1

            if k != 0:
                i = k +1
                k = 0
            else:
                i = i +1

    return listmax

def sort_heap(randomlist): 

    max_heap_tree = max_heap(randomlist)
    sorted_heap = []

    sorted_heap.append(max_heap_tree[0])

    while len(max_heap_tree) > 1: 

# the next highest number is found using the max_heap by removing the [0] element from the list 

        max_heap_tree = max_heap(max_heap_tree[1:])
        sorted_heap.append(max_heap_tree[0])

    return sorted_heap


randomlist = [10,15,20,25,30,35,40,45,50,55] 
sort_heap(randomlist)

I had put a counter in while loop and to get max heap with 10 nodes in the above example it took 19 iterations and overall to sort the complete list 60 iterations. Not sure if can be improved more.

Also, the way i am creating the max heap is literally how we would do it on paper.