how can I find the minumm of items which is less than a number from list of lists with heap?-CodePudding

I had a question in my exam today. Consider I have a list like this:

[[0, 0], [95, 1], [0, 5], [200, 3], [1000, 4], [300, 2]]

how can I find elements which their ele[0] values are less than a certain value and ele[1] is the minimum among them all? example: if input n=100? then [0, 0], [95, 1], [0, 5] have less ele[0] value than 100, and [0,0] is the minimum. so the output should be [0,0] The question wanted us to do it with a heap but I don't know how. any help would be appreciated.

CodePudding user response：

Here is a working solution:

from heapq import heappush as push, heappop as pop

def find_min_ele(lst, n):
    h = []
    for a, b in lst:
        if a < n:
            push(h, [b, a])  # reverse!
    return pop(h)[::-1]  # reverse again


>>> find_min_ele([[95, 1], [0, 5], [200, 3], [1000, 4], [300, 2]], 200)
[95, 1]

CodePudding user response：

To implement a min-heap in Python, you can use the heapq module, which provides functions for creating and manipulating min-heaps. Here is an example of how you can use a min-heap to find the element with the minimum value of ele[1] among the elements with ele[0] values less than a certain value:

import heapq

def find_min_ele(lst, n):
    # create a min-heap
    heap = []
    # add elements to the heap
    for ele in lst:
        if ele[0] < n:
            heapq.heappush(heap, ele[1])
    # find the minimum element
    min_value = heapq.heappop(heap)
    for ele in lst:
        if ele[1] == min_value:
            return ele

lst = [[0, 0], [95, 1], [0, 5], [200, 3], [1000, 4], [300, 2]]
n = 200
print(find_min_ele(lst, n))

In this example, the find_min_ele function takes a list of elements and a value n as arguments. It creates a min-heap and adds the values of ele[1] from the elements with ele[0] values less than n to the heap. Finally, it returns the minimum value from the heap by calling the heappop function.