Simple minheap in Python using List with Tuple (immutable) elements
up vote
0
down vote
favorite
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))]
python reinventing-the-wheel heap
edited 17 hours ago
Jamal♦
30.2k11115226
asked yesterday
mAndroid
1235
add a comment |
up vote
0
down vote
favorite
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))]
python reinventing-the-wheel heap
edited 17 hours ago
Jamal♦
30.2k11115226
asked yesterday
mAndroid
1235
The indentation looks wrong inheap_add_or_replace. Could you fix this, please? Also, you might want to say why you didn't use the built-inheapqmodule.
– Gareth Rees
yesterday
The reason for not using heapq is that it is part of an exercise to familiarise you with how the heap works.
– mAndroid
yesterday
The code in the post does not resemble a heap, it's just a list that gets sorted after every change. Are you sure this is what the exercise is asking you to implement? Maybe you need to quote the exercise so we can check what's it's asking.
– Gareth Rees
yesterday
The heap.pop() will always return the 0 element therefore returning the minimum.
– mAndroid
yesterday
add a comment |
up vote
0
down vote
favorite
up vote
0
down vote
favorite
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))]
python reinventing-the-wheel heap
edited 17 hours ago
Jamal♦
30.2k11115226
asked yesterday
mAndroid
1235
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))]
python reinventing-the-wheel heap
python reinventing-the-wheel heap
edited 17 hours ago
Jamal♦
30.2k11115226
asked yesterday
mAndroid
1235
edited 17 hours ago
Jamal♦
30.2k11115226
asked yesterday
mAndroid
1235
edited 17 hours ago
Jamal♦
30.2k11115226
edited 17 hours ago
Jamal♦
30.2k11115226
edited 17 hours ago
Jamal♦
30.2k11115226
30.2k11115226
asked yesterday
mAndroid
1235
asked yesterday
mAndroid
1235
asked yesterday
mAndroid
1235
1235
The indentation looks wrong inheap_add_or_replace. Could you fix this, please? Also, you might want to say why you didn't use the built-inheapqmodule.
– Gareth Rees
yesterday
The reason for not using heapq is that it is part of an exercise to familiarise you with how the heap works.
– mAndroid
yesterday
The code in the post does not resemble a heap, it's just a list that gets sorted after every change. Are you sure this is what the exercise is asking you to implement? Maybe you need to quote the exercise so we can check what's it's asking.
– Gareth Rees
yesterday
The heap.pop() will always return the 0 element therefore returning the minimum.
– mAndroid
yesterday
add a comment |
The indentation looks wrong inheap_add_or_replace. Could you fix this, please? Also, you might want to say why you didn't use the built-inheapqmodule.
– Gareth Rees
yesterday
The reason for not using heapq is that it is part of an exercise to familiarise you with how the heap works.
– mAndroid
yesterday
The code in the post does not resemble a heap, it's just a list that gets sorted after every change. Are you sure this is what the exercise is asking you to implement? Maybe you need to quote the exercise so we can check what's it's asking.
– Gareth Rees
yesterday
The heap.pop() will always return the 0 element therefore returning the minimum.
– mAndroid
yesterday
The indentation looks wrong in
heap_add_or_replace. Could you fix this, please? Also, you might want to say why you didn't use the built-in heapq module.– Gareth Rees
yesterday
The indentation looks wrong in
heap_add_or_replace. Could you fix this, please? Also, you might want to say why you didn't use the built-in heapq module.– Gareth Rees
yesterday
The reason for not using heapq is that it is part of an exercise to familiarise you with how the heap works.
– mAndroid
yesterday
The reason for not using heapq is that it is part of an exercise to familiarise you with how the heap works.
– mAndroid
yesterday
The code in the post does not resemble a heap, it's just a list that gets sorted after every change. Are you sure this is what the exercise is asking you to implement? Maybe you need to quote the exercise so we can check what's it's asking.
– Gareth Rees
yesterday
The code in the post does not resemble a heap, it's just a list that gets sorted after every change. Are you sure this is what the exercise is asking you to implement? Maybe you need to quote the exercise so we can check what's it's asking.
– Gareth Rees
yesterday
The heap.pop() will always return the 0 element therefore returning the minimum.
– mAndroid
yesterday
The heap.pop() will always return the 0 element therefore returning the minimum.
– mAndroid
yesterday
add a comment |
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
draft saved
draft discarded
Thanks for contributing an answer to Code Review Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f209274%2fsimple-minheap-in-python-using-list-with-tuple-immutable-elements%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
The indentation looks wrong in
heap_add_or_replace. Could you fix this, please? Also, you might want to say why you didn't use the built-inheapqmodule.– Gareth Rees
yesterday
The reason for not using heapq is that it is part of an exercise to familiarise you with how the heap works.
– mAndroid
yesterday
The code in the post does not resemble a heap, it's just a list that gets sorted after every change. Are you sure this is what the exercise is asking you to implement? Maybe you need to quote the exercise so we can check what's it's asking.
– Gareth Rees
yesterday
The heap.pop() will always return the 0 element therefore returning the minimum.
– mAndroid
yesterday