'(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

pythonalgorithmsortingheapheapsort


Solution 1:[1]

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.

Solution 2:[2]

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

Solution 3:[3]

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

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1 harold
Solution 2 spider
Solution 3 spider

Related Questions