3
\$\begingroup\$

NOTE: I am beginner in Python

I learnt the Heap sort today and tried my own implementation using Python. Can i get feedback for my code and areas of improvement. I have tried to add comments inline, but if still something is unclear, then i will add more comments.

 def max_heap(listmax):

    i = 1

#   if there is only one node, so thats is the max heap
#   for only 1 node, it wont go inside while loop and max heap will be node itself

    while i <= len(listmax) -1:

#   for 2 nodes of more, the parent is checked against child
#   when there are 2 nodes, i will have max 1 value = len(listmax) - 1

#   j is actually the parent of i, i can have 2 children which will have odd and even index
#   for eg. if 3 nodes, i can be 0,1,2  so 0 is parent and 1,2 will be children

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

#   here the listmax[i] will have the value of child node and listmax[j] has value of parent
#   if the parent > children, then else is executed which moves to the next child of the parent

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

#   the i > 2 is there because then only, the children can become parents, and hence i make
#   the children as parents and compare it further up
#   the children are made parent by the below logic

            if i > 2:
                if i%2 == 0:
                    i = int(i/2 -1)
                else:
                    i = int(i//2)
            else:
                i = i +1
        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,30,12,15,20,17,20,32] 
sort_heap(randomlist)
\$\endgroup\$
1
  • \$\begingroup\$ I rolled back your last edit. After getting an answer you are not allowed to change your code anymore. This is to ensure that answers do not get invalidated and have to hit a moving target. If you have changed your code you can either post it as an answer (if it would constitute a code review) or ask a new question with your changed code (linking back to this one as reference). Refer to this post for more information \$\endgroup\$ Mar 3, 2020 at 16:03

2 Answers 2

3
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ Thanks for the feedback. Yes i worked on improving my code. I have literally coded it they way, as if someone would do it on paper. I counted the iterations also and i cant think of any iteration which i can save now. Thanks for your feedback and would appreciate more constructive feedback. Thanks \$\endgroup\$
    – prabh
    Mar 3, 2020 at 15:56
  • 1
    \$\begingroup\$ @prabh manipulating i in an even more complex way is not what I meant. You can propably make it faster that way.. but there is a much simpler way: loop over the list (just a normal plain old for-loop) and perform "bubble up" for each of the items (you can make that its own function even, why not) independently of the outer loop. \$\endgroup\$
    – harold
    Mar 3, 2020 at 16:12
0
\$\begingroup\$

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.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ You still use the same max_heap function to construct the initial heap, and for each step of bubbling down. Once you have a heap, you need to take advantage of that to make sure each individual element only needs log time. Look up the "heapify" function and how it is different. \$\endgroup\$ Mar 3, 2020 at 19:12
  • 1
    \$\begingroup\$ @KennyOstrom i think i got your point now. Once i have the max heap, i just need to take the max element and then take the last node to position 0 and rearrange the heap which will take maximum of iterations as the height of the tree. \$\endgroup\$
    – prabh
    Mar 3, 2020 at 21:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.