Trouble implmenting Minheap algorithm!

[damo87]

Hi guys, i'm doing a peice of coursework for uni where we are required to implement a Min-heap/priority queue for calculating the Minimum Spanning Tree. In a min heap, the parent's value needs to be smaller than that of its two children. I've tried to implement this,giving the following list as input: test=[17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1].. hoping to get somthing like [1,2,3,4,5,6,7,8,9... etc] as output. I got [1, 2, 6, 3, 8, 7, 4, 10, 9, 15, 16, 12, 5, 11, 14, 17, 13] which is mostly right apart from the positions of elements 2,6 and 12 (0-based numbering). The 1D array represents the heap like so: [root,child1,child2,child1ofchild1,child2ofchild1 etc].

Anyway, i think the algorthim im using is coded right but im not getting the output i should. If anyone could give me some help here i'd be really greatful as ive been fiddling away for ages with this and im pretty sure its somthing small and stupid that's meaning some of the nodes arnt in the right order. Cheers guys.

Im attaching the code as a txt file cos the forum doesnt allow uploading of .py files, just change the extension and it should run!

[BearofNH]

Using the secret [code=Python]... [/code] tags, we get:

def main():
    def Parent(i):
        return i/2
    def Left(i):
        return 2*i
    def Right(i):
        return 2*i+1

    def Heapify(A, parent, last): 
        left = Left(parent)
        right = Right(parent)
        if left <= last and A < A[parent]:
            smallest = left
        else:
            smallest = parent
        if right <= last and A < A[smallest]:
            smallest = right
        if smallest != parent:
            A[parent], A[smallest] = A[smallest], A[parent]
            Heapify(A, smallest, last)
        print A
        return A

    def HeapLength(A):
        return len(A)-1
    
    def BuildHeap(A): # build a heap A from an unsorted array
        n = HeapLength(A)
        for i in range(n/2,-1,-1):
            Heapify(A,i,n)
        print A
        return A

    def HeapSort(A): # use a heap to build sorted array from the end

        BuildHeap(A)
        HeapSize=HeapLength(A)
        
        for i in range(HeapSize,0,-1):
            A[i],A[0]=A[0],A[i] # Swap 1st and last elements of the array
            HeapSize=HeapSize-1 # shrink heap size by 1 to get next largest element
            Heapify(A,0,HeapSize)

    test=[17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1]
    BuildHeap(test)
    
main()

Now to have a look...

[BearofNH]

The 1D array represents the heap like so: [root,child1,child2,child1ofchild1,child2ofchild1 etc].

I don't think this is true! Since the list is 0-based, child1 is the child of root, but child2 is the child of child1. (You know, 2/2 is 1, not 0 :-). This skews things right from the start.

One way around this is to add a dummy root at the start and avoid displaying it at the end. For example, I replaced the end of your code with:

test=[17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1]
    h = BuildHeap([0] + test)
    for i in range(HeapLength(h), 1, -1):
        print "%2d parent is %2d" % (h[i], h[Parent(i)])
    
main()

and the output is

... <intermediate steps omitted> ...
[0, 1, 2, 3, 9, 7, 5, 4, 10, 17, 8, 13, 6, 12, 15, 11, 14, 16]
16 parent is 10
14 parent is 10
11 parent is  4
15 parent is  4
12 parent is  5
 6 parent is  5
13 parent is  7
 8 parent is  7
17 parent is  9
10 parent is  9
 4 parent is  3
 5 parent is  3
 7 parent is  2
 9 parent is  2
 3 parent is  1
 2 parent is  1

... which, if you draw the pyramid from the bottom up, looks fine.

Another way around this is to use pointers and data structures but I assume there's a reason you're not already doing that.

[damo87]

It works!!! :D that problem was really doing my head in, its funny how such tiny things can really mess up your program haha Thanks so much for your help!