Removing elements of the heap/priority queue using remove

[Conscht]

Hi,

I think there is an issue in greedy_many_to_many_matching.py and the way we decide on our max score elements.

We have a Priority-Queue that is based on a heap. Now, during the for-loop, we handle the heap as a simple list and directly remove elements from it. Python handles queue removals by simply compressing it, shifting every element right to the removed element, by one to the left.
However, this is not a safe operation on a heap, and will break the ordering of the heap/priority-queue

This can cause wrong elements to be at the top of the heap/priority queue.

greedy_many_to_many_matching.py 108-L142

        for o_clr, o_gt_id, o_pred_id in q.queue:
            denominator_gt = float(np.sum(gt_skel[o_gt_id]))
            if o_gt_id == gt_id:
                # remove old clRecall entry
                q.queue.remove((o_clr, o_gt_id, o_pred_id))
                if not only_one_gt:
                    # add updated clRecall entry
                    o_clr_new = np.sum(np.logical_and(gt_avail[o_gt_id], instance_mask(pred_labels, o_pred_id))) / denominator_gt
                    q.put(((-1) * o_clr_new, o_gt_id, o_pred_id))

            if o_pred_id == pred_id:
                # remove old clRecall entry
                q.queue.remove((o_clr, o_gt_id, o_pred_id))
                if not only_one_pred:
                    # add updated clRecall entry
                    o_clr_new = np.sum(np.logical_and(gt_skel[o_gt_id], pred_avail[o_pred_id])) / denominator_gt
                    q.put(((-1) * o_clr_new, o_gt_id, o_pred_id))

[Conscht]

Here is a small edit to make it maybe more graspable:

We use a Python PriorityQueue(). The Python PriorityQueue is implemented using the heapq module
(see StackOverflow).

From the Python Doc:

"With a priority queue, the entries are kept sorted (using the heapq module) and the lowest valued entry is retrieved first"

This heap structure allows us mainly two operations to alter the queue, without destroying the heap invariant (always keeping the item with the highest/lowest priority at the top): _get()_ and _put(element)_.

However, since heapq is implemented using Lists, we could also bypass the interface of the heapq, and access the remove(element) function of the List() class. This removes an element from a List and then closes the gap by shifting the remaining elements together (https://stackoverflow.com/questions/5484929/removing-an-item-from-a-priority-queue).

We will basically take a heap, but treat it as a list (but our heap is not sorted the same way you would sort a List). This explains why the PriorityQueue is still working after the remove call, but the heap will not be sorted correctly anymore.

Possible solutions would be either LazyHeap or calling heapify after removing an arbitrary element of the heap. Both are feasible, but I decided to do a LazyHeap due to possible complexity benefits (we must not call remove and heapify every time, which each are in O(n)). Instead we call only pop which is O(log(n)) and and marking nodes invalid, which is O(1).