CODEWITHSUNDEEP
pythonalgorithmsortingheapheapsort
Gambino Adultish
Gambino Adultish

Reputation: 3

(Python) Heapsort min heap implementation for Non Increasing Order Sorting. What am I doing wrong?

def min_heapify(A,k, n):
    left = 2*k +1
    right = 2*k +2
    n=int(len(A))
    if left < n and A[left] < A[k]:
        smallest = left
    else:
        smallest = k
    if right< n and A[right] < A[smallest]:
        smallest = right
    if smallest != k:
        A[k], A[smallest] = A[smallest], A[k]
        min_heapify(A, smallest, n)


def build_min_heap(A):
    n = int((len(A)//2)-1)
    for k in range(n, -1, -1):
        min_heapify(A,k,n)

def heapsort(A):
    n= int(len(A)) 
    build_min_heap(A)
    for i in range(n-1, 0, -1):
        A[i], A[0] = A[0], A[i]
        min_heapify(A, i, 0)


A = [8,7,9,1,4,6,3]
heapsort(A)
print(A)

The output i am getting is :[4, 3, 1, 8, 6, 9, 7] and I want the array or list to be sorted in Non increasing order, built my min_heapify, build_min_heap functions and even the heapsort function like the default pseudocode. What did I do wrong here? Please help me out

Upvotes: 0

Views: 663

Answers (3)

spider_Malaya
spider_Malaya

Reputation: 13

arr = [3,4,5,1,2,3,7,8,90,67,31,2,5,567]

# inheap_sort will lead the array to descending order using min heap
def minheap(arr,p):
    for i in range(len(arr)-p):
        if i > 0:
            child = i
            parent = (i+1)//2 -1
            while arr[parent]>arr[child] and child !=0:
                arr[parent],arr[child]=arr[child],arr[parent]
                child = parent
                parent = (parent+1)//2 -1
                

def heapsort(arr):
    for i in range(len(arr)):
        minheap(arr,i)
        arr[0], arr[len(arr)-i-1]=arr[len(arr)-i-1], arr[0]
    return arr

print(heapsort(arr))

this methord is for minheap

Upvotes: 0

spider_Malaya
spider_Malaya

Reputation: 13

arr = [3,4,5,1,2,3,0,7,8,90,67,31,2,5,567]
# max-heap sort will lead the array to assending order
def maxheap(arr,p):
    
    for i in range(len(arr)-p):
        if i > 0:
            child = i
            parent = (i+1)//2 - 1
            
            while arr[child]> arr[parent] and child !=0:
                arr[child], arr[parent] = arr[parent], arr[child]
                child = parent
                parent = (parent+1)//2 -1
                
    
def heapsort(arr):
    for i in range(len(arr)):
        maxheap(arr,i)
        arr[0], arr[len(arr)-i-1]=arr[len(arr)-i-1],arr[0]
        
    return arr
        

print(heapsort(arr))

see this I think it will help you

Upvotes: 0

user555045
user555045

Reputation: 64933

There are a couple of bugs.

First, min_heapify cannot use n=int(len(A)), it must respect the size of the heap that is passed in. Otherwise, in the second phase of the algorithm, it will heapify over the end of the array where the sorted elements are, which sort of absorbs them back into the heap.

But, first-and-a-half, when that is fixed then build_min_heap no longer builds a min-heap. That's because it passes the wrong size: it passes n, but n in that context is less than half the size of the heap. Previously the first bug would compensate for this, but no longer. Solution: pass len(A) as the size here.

Second, in the second phase of the algorithm, min_heapify(A, i, 0) has the second and third parameters switched around. Naturally, i is the size of the heap, and 0 is the index to be heapified, but they are passed the other way around: heapifying item i of a 0-size heap doesn't even make sense.

After I fixed those things, I got the right result, but I would not dare to say that the code is now bug-free, there may yet be something else lurking in the code that I did not find.

Upvotes: 1

Related Questions