Heap sort Python implementation

Question

def heap_sort(nos):
    global size
    size = len(nos)
    print "the size of the List is : %d " %size
    Build_heap(size,nos)
    for i in range(size-1,0,-1):
        nums[0],nums[i] = nums[i],nums[0]
        size = size-1
        print "\n", nums
        heapify(nos,i,size)
    print "heap sort array:" ,nums

def left_child(i):
    return 2*i+1

def right_child(i):
    return 2*i+2

def heapify(nums,i,size):
    l = left_child(i)
    r = right_child(i)
    if l <= size and r <= size:
        if r != size:
            if nums[l] >= nums[r]:
                max = nums[l]
                max_index = l
            elif nums[l] <= nums[r]:
                max = nums[r]
                max_index = r
            if nums[i] >= max:
                print nums
                return
            elif nums[i] <= max:
                nums[i],nums[max_index] = max,nums[i]
                heapify(nums,max_index,size)
        else:
            nums[i],nums[l] = nums[l],nums[i]
            print nums

# build a heap A from an unsorted array          
def Build_heap(size,elements):
    iterate = size//2-1
    for i in range(iterate,-1,-1):
        print "In %d iteration" %i
        heapify(elements,i,size)
    print "heapified array is : " ,elements


if __name__ == '__main__':
    #get input from user
    nums = [6,9,3,2,4,1,7,5,10]
    #sort the list
    heap_sort(nums)

Output which I get is something like this:

the size of the List is : 9 
In 3 iteration
[6, 9, 3, 10, 4, 1, 7, 5, 2]
In 2 iteration
[6, 9, 7, 10, 4, 1, 3, 5, 2]
In 1 iteration
[6, 10, 7, 9, 4, 1, 3, 5, 2]
[6, 10, 7, 9, 4, 1, 3, 5, 2]
In 0 iteration
[10, 6, 7, 9, 4, 1, 3, 5, 2]
[10, 9, 7, 6, 4, 1, 3, 5, 2]
[10, 9, 7, 6, 4, 1, 3, 5, 2]
heapified array is :  [10, 9, 7, 6, 4, 1, 3, 5, 2]
heap sort array: 
[9, 7, 6, 4, 1, 3, 5, 2, 10]

I tried implementing a heap sort algorithm in python. The final output is not sorted. There is something wrong in the heapify operation which I tried to figure out, but I couldn't find it.

Can someone point out what's wrong in my code and propose a solution for it?

Pro tip: Python can assign to two variables with one operation: nums[i], nums[max_index] = max, nums[i] and nums[i], nums[l] = nums[l], nums[i]. — Martijn Pieters
– Martijn Pieters, Commented Jul 1, 2013 at 7:36

falsetru · Accepted Answer · 2013-07-01 08:24:50Z

0

The first item(0) was swaped with the last item. To keep max-heap invairant, you should call heapify with 0.

def heap_sort(nos):
    size = len(nos)
    build_heap(size,nos)
    for i in range(size-1,0,-1):
        nums[0],nums[i] = nums[i],nums[0]
        size -= 1
        heapify(nos, 0, size) # <--- i -> 0

answered Jul 1, 2013 at 8:24

falsetru

371k69 gold badges769 silver badges659 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

vr22 Over a year ago

why does my above code doesnt work if i give input as list of lists like nums = [[5,10,15,20],[6,3,16,19],[2,9,26,40],[8,22,23,24]]

falsetru Over a year ago

What do you want your code to produce as output? If you want [2,3,5,6,8,9, .....], flatten list to 1st dimension.

vr22 Over a year ago

suppose the above code is used to construct min-heap in k-way merge sort implementation taking k-sorted sublist as input.am storing that k-sorted sublist inside a list. In that case its not working

user5818263 · Accepted Answer · 2016-01-20 23:49:52Z

The following is my PYTHON implementation. If the program is "heapsort.py", an example to run it is "python heapsort.py 10", to sort 10 randomly generated numbers.

The validation code is near the end of the program, to verify the correctness of the function, heapsort().

#!/bin/python
#
# TH @stackoverflow, 2016-01-20, HeapSort
#
import sys, random


def pushdown( A, root, size_of_A ):
    M = root * 2
    if(M <= size_of_A):
        if(size_of_A > M):
            if(A[M - 1] < A[M]):
                M += 1

        if(A[root - 1] < A[M - 1]):
            A[root - 1], A[M - 1] = A[M - 1], A[root - 1]
            pushdown(A, M, size_of_A)


def heapsort( H ):
    for i in range(len(H)/2, 0, -1):
        pushdown(H, i, len(H))

    for i in range(len(H) - 1, 0, -1):
        H[i], H[0] = H[0], H[i]
        pushdown(H, 1, i)

    return H


number_to_numbers = int(sys.argv[1])
X = [ random.randint(0, number_to_numbers) for i in range(number_to_numbers) ]
Y = X
print Y
print heapsort(X)
print sorted(Y)

Collectives™ on Stack Overflow

Heap sort Python implementation

2 Answers 2

3 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related