CODEWITHSUNDEEP
pythonalgorithmsortingheap
Tom
Tom

Reputation: 21

Is This a Valid HeapSort?

For the past 6 hours, I've been reading tutorials and academic material on constructing a heapsort. I finally have prototyped something in python that sorts a list of integers. However, I'm not entirely sure whether or not my solution constitutes a valid heapsort. It's a very simplistic solution and can definitely be improved upon, but I'm wondering whether it is valid at all. Confusingly, everyone seems to have their own 'preferred' way of implementing this algorithm.

Many thanks in advance.

def heapsort(array):
    array = heapify(array)
    array = insert(array, 9999)
    print(array)

def heapify(array):
    end = len(array)
    i = 0
    j = 0
    while i < end:
        while j < end:
            if array[i] > array[j]:
                array = swap(array, i, j)
            j += 1
        i += 1
        j = i
    return array

def insert(array, x):
    array.append(x)
    return heapify(array)


def swap(array, a, b):
    temp = array[a]
    array[a] = array[b]
    array[b] = temp
    return array

def main(array):
    heapsort(array)

if __name__ == '__main__':
    array = [3, 1, 2, 4, 6, 7, 9, 0]
    main(array)

Upvotes: 2

Views: 142

Answers (2)

moreON
moreON

Reputation: 2008

What you have written appears to be a Selection Sort.

A heap sort arranges the array into a heap (most simply a binary heap) which is a structure in which the time to find the smallest element is O(1) and to remove the smallest element is O(log n) and insertion of an element is also O(log n). It then repeatedly takes the smallest element of this to produce the sorted order.

Upvotes: 2

WestCoastProjects
WestCoastProjects

Reputation: 63062

Your heapify() should be comparing elements of Parent/Child within the heap (tree structure). Their relative location within the array is 

ChildIndex = 2 * Parent Index + [0|1]  # two children per parent

in terms of index into the array. That is not evident in your implementation.

Upvotes: 2

Related Questions