Will a Fibonacci heap be optimal for my task on hierarchical clustering?

Question

I am working on a class project that deals with image segmentation. Given an initial oversegmentation of the image, we are planning to merge pairs together via agglomerative clustering.

1. We will firstly iterate through clusters and push the pair-wise distance and the ID of these pairs of clusters (used for referencing when updating distance due to a merge operation) into a data structure.

2. At each iteration, the pair of clusters with the minimum distance will be merged and the node that stores this distance will be deleted.

3. All other nodes that were originally connected to said pair will have their distance recomputed and information updated (i.e. it is now connected to cluster a-b instead of cluster a).

We have been advised to use a Fibonacci heap as it can find the minimum key in O(1). However, because there is still the issue of searching for neighbors and updating their distances, I was wondering if Boost's implementation of Fibonacci heaps allows me to locate a certain node in O(1) if I have a label for each node?

TLDR: I'd like to know if there is a data structure that can efficiently locate nodes and delete min.

Answer 1

According to a summary made by John Ahlgren of an SO q&a about performance of std containers :

+------------------+---------------------+---------------------+---------------------+------------------+----------------------+
| Container        | Insertion           | Access              | Erase               | Find             | Persistent Iterators |
+------------------+---------------------+---------------------+---------------------+------------------+----------------------+
| vector / string  | Back: O(1) or O(n)  | O(1)                | Back: O(1)          | Sorted: O(log n) | No                   |
|                  | Other: O(n)         |                     | Other: O(n)         | Other: O(n)      |                      |
+------------------+---------------------+---------------------+---------------------+------------------+----------------------+
| deque            | Back/Front: O(1)    | O(1)                | Back/Front: O(1)    | Sorted: O(log n) | Pointers only        |
|                  | Other: O(n)         |                     | Other: O(n)         | Other: O(n)      |                      |
+------------------+---------------------+---------------------+---------------------+------------------+----------------------+
| list             | Back/Front: O(1)    | Back/Front: O(1)    | Back/Front: O(1)    | O(n)             | Yes                  |
| forward_list     | With iterator: O(1) | With iterator: O(1) | With iterator: O(1) |                  |                      |
|                  | Index: O(n)         | Index: O(n)         | Index: O(n)         |                  |                      |
+------------------+---------------------+---------------------+---------------------+------------------+----------------------+
| set / map        | O(log n)            | N/A                 | O(log n)            | O(log n)         | Yes                  |
+------------------+---------------------+---------------------+---------------------+------------------+----------------------+
| unordered_set    | O(1) or O(n)        | O(1) or O(n)        | O(1) or O(n)        | O(1) or O(n)     | Pointers only        |
| unordered_map    |                     |                     |                     |                  |                      |
+------------------+---------------------+---------------------+---------------------+------------------+----------------------+
| priority_queue   | O(log n)            | O(1)                | O(log n)            | N/A              | N/A                  |
+------------------+---------------------+---------------------+---------------------+------------------+----------------------+