Krdytkyu

I'm currently doing a course on EDX and one of the tasks is the implementation of a simple min-heap.

The heap must be implemented using a list of tuples, which are immutable so can't be changed in place.

The first element of the tuple is the key. The second element is the variable to be checked for minimum value. Element 3 is extraneous.

My solution is below but as I'm new to Python I'd like to know how a more experienced programmer would implement it but with the existing constraints of a list of tuples - no other data structures can be used.

def heap_add_or_replace(heap, triplet):

    match = 0

    for tup in heap[:]:

        if tup[0] == triplet[0]:

            match += 1

            if tup[1] > triplet[1]:

                heap.remove(tup)

                heap.append(triplet)

                break

    if match == 0:

        heap.append(triplet)



    heap.sort(key=lambda x: x[1])

The tests from the course are included below:

#

# AUTOGRADER TEST - DO NOT REMOVE

#



triplet_heap=list()



heap_add_or_replace(triplet_heap,((2,3),0.9,(1,0)))

print("the new heap is: "+str(triplet_heap))



heap_add_or_replace(triplet_heap,((7,2),0.3,(2,2)))

print("the new heap is: "+str(triplet_heap))



heap_add_or_replace(triplet_heap,((3,2),1,(2,2)))

print("the new heap is: "+str(triplet_heap))



print("the new heap is: "+str(triplet_heap))



heap_add_or_replace(triplet_heap,((7,2),0.2,(2,3)))

print("the new heap is: "+str(triplet_heap))



heap_add_or_replace(triplet_heap,((1,2),0.3,(2,3)))

print("the new heap is: "+str(triplet_heap))



heap_add_or_replace(triplet_heap,((1,2),0.1,(2,3)))

print("the new heap is: "+str(triplet_heap))



heap_add_or_replace(triplet_heap,((1,2),0.05,(2,0)))

print("the new heap is: "+str(triplet_heap))



heap_add_or_replace(triplet_heap,((4,6),2,(2,3)))

print("the new heap is: "+str(triplet_heap))



heap_add_or_replace(triplet_heap,((1,2),0.01,(2,0)))

print("the new heap is: "+str(triplet_heap))



heap_add_or_replace(triplet_heap,((4,6),9,(2,3)))

print("the new heap is: "+str(triplet_heap))

and the expected results:

the new heap is: [((2, 3), 0.9, (1, 0))]

the new heap is: [((7, 2), 0.3, (2, 2)), ((2, 3), 0.9, (1, 0))]

the new heap is: [((7, 2), 0.3, (2, 2)), ((2, 3), 0.9, (1, 0)), ((3, 2), 1, (2, 2))]

the new heap is: [((7, 2), 0.3, (2, 2)), ((2, 3), 0.9, (1, 0)), ((3, 2), 1, (2, 2))]

the new heap is: [((7, 2), 0.2, (2, 3)), ((2, 3), 0.9, (1, 0)), ((3, 2), 1, (2, 2))]

the new heap is: [((7, 2), 0.2, (2, 3)), ((1, 2), 0.3, (2, 3)), ((2, 3), 0.9, (1, 0)), ((3, 2), 1, (2, 2))]

the new heap is: [((1, 2), 0.1, (2, 3)), ((7, 2), 0.2, (2, 3)), ((2, 3), 0.9, (1, 0)), ((3, 2), 1, (2, 2))]

the new heap is: [((1, 2), 0.05, (2, 0)), ((7, 2), 0.2, (2, 3)), ((2, 3), 0.9, (1, 0)), ((3, 2), 1, (2, 2))]

the new heap is: [((1, 2), 0.05, (2, 0)), ((7, 2), 0.2, (2, 3)), ((2, 3), 0.9, (1, 0)), ((3, 2), 1, (2, 2)), ((4, 6), 2, (2, 3))]

the new heap is: [((1, 2), 0.01, (2, 0)), ((7, 2), 0.2, (2, 3)), ((2, 3), 0.9, (1, 0)), ((3, 2), 1, (2, 2)), ((4, 6), 2, (2, 3))]

the new heap is: [((1, 2), 0.01, (2, 0)), ((7, 2), 0.2, (2, 3)), ((2, 3), 0.9, (1, 0)), ((3, 2), 1, (2, 2)), ((4, 6), 2, (2, 3))]