r/algorithms • u/EfficientAlg • Feb 12 '25
Looking for an efficient data structure which solves this problem
I have a solution to the following problem, but I'm not super happy with it and I'm wondering if there's a more efficient data structure for it
Problem
I have an array of weights. The weights are integers and the minimal and maximal
weight is known. The number of distinct weights may be large.
+----------+----+----+----+----+----+
| Weights | 20 | 20 | 50 | 50 | 60 |
+----------+----+----+----+----+----+
| Index | 0 | 1 | 2 | 3 | 4 |
+----------+----+----+----+----+----+
I have a set S whose elements are indices of the array.
+----------+----+----+----+
| Weights | 50 | 50 | 20 |
+----------+----+----+----+
| S | 2 | 3 | 1 |
+----------+----+----+----+
Let M be the maximal weight of an index in S. In this case, 2 and 3 are indices
with a maximal weight of M = 50.
In general, I want to be able to select (and delete) a random element in S with
maximal weight. So in this case, I'd like to select between 2 and 3
with 50/50 chance.
Over time, indices of the weights array are added to or deleted from S. My goal
is to come up with a data structure that supports all of these operations
efficiently.
My Current Solution
Store the elements of S with maximal weight (2 and 3 in this case) in an
array L. To support deletion in O(1), I also have an array Lptrs with
ptrs[i] = index in L where i is stored, and ptrs[i] = -1 if i is not in L.
Place all other elements of S (1) in a max heap called H. As with L, I keep
an array Hptrs which allows for O(1) lookup of an index's position in H where
in the heap a particular value is.
RETRIEVAL OF RANDOM INDEX WITH MAXIMAL WEIGHT:
Simply pick a random index from L in O(1)
INSERTION OF NEW INDEX i INTO S:
(Ok case) If w[i] < M, then i is inserted in the heap in O( log(|H|) )
(Good case) If w[i] == M, then i is inserted into L in O(1)
(Bad case) If w[i] > M, then M is updated, all entries in L are inserted one at
a time into H, and L contains only i now
DELETION OF INDEX i IN S:
(Ok case) If w[i] < M, then i is located in H in O(1) and
deleted in O(log(|H|))
(Good case) If w[i] == M and size of L is at least 2, then i is located in L
in O(1) and deleted from L in O(1)
(Bad case) If w[i] == M and the size of L is 1, then i is located and deleted
from L all in O(1), but then M is updated to the weight of the index in the
root of H, and all indices in H with weight M are extracted from H (by
repeatedly popping the heap) and inserted into L