I have a list (or heap) of elements and I want to replace the element with the lowest value with a new element of higher value. However if there are multiple elements in the heap with this lowest value, I expect to replace the last element.
Example 1 (works as expected):
input:
n = 7
new_element = 1
hlist = [0 for x in range(n)]
hp.heapreplace(hlist,new_element)
hlist
output:
[0, 0, 0, 0, 0, 0, 1]
Example 2 (doesn't work as expected):
input:
n = 10
new_element = 1
hlist = [0 for x in range(n)]
hp.heapreplace(hlist,new_element)
hlist
output:
[0, 0, 0, 0, 0, 0, 1, 0, 0, 0]
The expected output is:
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
With n in [1,2,...,9,10] it works when n in [1, 2, 3, 6, 7].
The order you see inside a heap, is not necessarily ascending or descending inside the list that stores the values. So you need to sort it out before printing. According to the documentation, you can define a function named heapsort to sort the heap.
from heapq import *
def heapsort(iterable):
h = []
for value in iterable:
heappush(h, value)
return [heappop(h) for i in range(len(h))]
n = 7
new_element = 1
hlist = [0 for x in range(n)]
heapify(hlist)
heapreplace(hlist,new_element)
print(heapsort(hlist))
and the output will be :
[0, 0, 0, 0, 0, 0, 1]
Also you can solve this problem using lists.
n = 7
new_element = 1
hlist = [0 for x in range(n)]
min_value = min(hlist)
for i in range(n-1,-1,-1):
if hlist[i]==min_value:
hlist[i] = new_element
break
and the output will be :
[0, 0, 0, 0, 0, 0, 1]