28

You can achieve constant amortized time per operation by keeping a dynamically-sized array $A$ (using the doubling/halving technique). To insert an element append it at the end. To implement remove_random() generate a random index $k$ between $1$ and $n$, swap $A[k]$ with $A[n]$ and delete (and return) $A[n]$. If you want a non-amortized worst-case bound on ...


15

Since you clearly don't care about the order of elements changing, I think the simplest approach is to use a resizable array (like C++'s std::vector or Java's java.util.ArrayList). When you remove an element, if it's not the last element, you just move the last element to take its place. That gives amortized-constant-time add and constant-time remove_random. ...


9

Another solution that provides amortized constant time operations is to use a dynamic array with insertion and removal at the end, just as in Steven's answer, but swap the last element with a random one after insert, instead of before removal as in Steven's method. That is, instead of doing what Steven suggests (in pseudocode): public method insert(element): ...


5

Based on standard usage of the terms, a heap is a specific data structure, with a specific representation in memory. A priority queue is an abstract data type: it identifies some operations that must be supported by the data structure, but does not itself describe any particular data structure. You can use a heap to implement the priority queue operations. ...


2

A random bijective function should satisfy this property with high probability for any specific set of indices. So, I suggest you use a random bijection on $[n^2]$. If $n$ is very large, you can compute this random bijection efficiently using format-preserving encryption, or by using a Feistel network with arithmetic modulo $n$ instead of XOR (treat the ...


1

You can append all 'r' nodes to the initial empty queue. Instead of checking whether the front node is the single destination node, check whether the front node is in the set of all destination nodes. With the two extensions above, the Lee algorithm will be able to find the shortest distance between the closest pair of 'r' and 'b' nodes in $O(MN)$ time. ...


1

Consider a list and let $e,f,g$ be three consecutive elements. Each element stores a value and has a "forward" pointer to the next element. Additionally, if the list is doubly linked each element also has a "backward" pointer to the previous element. Consider a singly linked list first. If you want to delete element $f$, then you need to ...


1

"Any element in the hash table will be selected with probability $\frac{1}{mL}$" is slightly confusing. It should be "Any pair of $(s, x)$, where $s$ is a slot in the hash table and $x$ is an index, $1\le x\le L$ will be selected with probability $\frac{1}{mL}$". There are $m$ choices for $s$ and $L$ choices for $x$. Since these two ...


1

Let $\phi$ be a CNF on $n$ variables $x_1,\ldots,x_n$. We construct a set of partial preorders over $V = \{a_1,b_1,\ldots,a_n,b_n\}$ as follows: For any $y,z \in V$ such that $y \neq z$, the partial preorder $y = z$. For each $i < n$, the four partial preorders \begin{align} a_i &> a_{i+1} & b_i &> a_{i+1} \\ a_i &> b_{i+1} & ...


Only top voted, non community-wiki answers of a minimum length are eligible