current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
up vote 5 down vote favorite

Please review the following in-place implementation of Heapsort in Python:

def heapsort(l):
    def plunge(l, i, n):
        lchild = 2 * i + 1
        while lchild < n:
            rchild = lchild + 1
            if rchild < n and l[lchild] < l[rchild]:
                child = rchild
            else:
                child = lchild

            if l[i] > l[child]: break

            l[i], l[child] = l[child], l[i]
            i, lchild = child, 2 * child + 1

    for i in range(len(l) // 2, -1, -1):
        plunge(l, i, len(l))

    for i in range(len(l) - 1, -1, -1):
        l[0], l[i] = l[i], l[0]
        plunge(l, 0, i)
share|improve this question
up vote 1 down vote accepted
+50

Your code is mostly good, only minor improvements are possible:

Use a conditional expression in place of a statement

A conditional statement, like the one you used may execute two completely different branches, instead a conditional expression can only return a value. This simplifies and shortens code a bit:

if rchild < n and l[lchild] < l[rchild]:
    child = rchild
else:
    child = lchild

Becomes:

child = rchild if rchild < n and l[lchild] < l[rchild] else lchild

To make it clear that you are just deciding what the value of child should be and nothing else.

Give nice names to public arguments

l is one letter long and is easily confused with 1, at least at small font sizes. Formal parameters names are the first form of documentation and should be given though. For example I suggest list_ or xs (a FP convention).

Write an additional helper: heapify

Both Wikipedia and Rosetta Code make use of the heapify helper, writing it into your code will make it more readable by making it similar to these descriptions.

Also the additional function will make it more clear that a heap is being created at first and then the actual sorted-list construction begins by taking elements from the heap.

share|improve this answer
up vote 1 down vote

Details :

Idiom

It seems like sift_down is a more common name than plunge. It might be a good option to use the usual vocabulary.

Reversed loop

Probably a personal preference but I find range(len(l) - 1, -1, -1) pretty hard to understand at first and I'd rather read reversed(range(len(l))).

share|improve this answer
up vote 1 down vote 
        rchild = lchild + 1
        if rchild < n and l[lchild] < l[rchild]:
            child = rchild
        else:
            child = lchild

This caught my eye because rchild is only ever used here. What if we inline it, then see if we can refactor differently?

if lchild + 1 < n and l[lchild] < l[lchild+1]:
    child = lchild + 1
else:
    child = lchild

...is the straight in-lining. So now refactor:

child = lchild
if lchild + 1 < n and l[lchild] < l[lchild+1]:
    child += 1

or maybe do it in reverse:

child = lchild + 1 # see if right child is usable
if child >= n or l[lchild] >= l[child]:
    # not usable, fall back to left child
    child = lchild

..which brings me to my next comment: your lack of comments. Just like choosing good names, comments can fill in the gaps and elucidate why something is done, from a summary point of view, since the code itself explains what is being done.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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