Questions tagged [data-structures]
Questions about ways of storing data so that it can be used advantageously by algorithms.
2,226 questions
0
votes
0
answers
23
views
Why is the universal hash function defined as Hp,m={ha,b(k)∣a,b∈{0,…,p−1},a=0}?
I understand the basic division hash function h(k)=k mod m, and the use of this function
but I don’t understand why the universal hash function introduces the parameters a and b and uses a prime ...
- 11
0
votes
0
answers
33
views
What is the name and theoretical basis for a Treap/RBST variant with a probabilistic, size-based merge?
I'm exploring data structures suitable for persistent applications. A key use case I have is splitting a subsegment from a tree, copying it, and then merging these copies into other data structures.
...
- 1
0
votes
1
answer
75
views
Counting Number of Complete Binary Trees with n Nodes
I know that the number of different complete binary tree structures (unlabeled) for n nodes is basically 1, because the structure is fixed.
Now I am trying to find the number of labeled complete ...
- 91
2
votes
0
answers
47
views
How does the equation to index non-leaf nodes of a binary tree 'array' in max-heap work for unbalanced binary trees?
According to Wikipedia's entry on binary heaps:
The Build-Max-Heap function that follows, converts an array A which stores a complete binary tree with n nodes to a max-heap by repeatedly using Max-...
- 123
0
votes
0
answers
118
views
Number of lexicographical swaps to make the array non decreasing
A lexicographical swap is defined as: At each step, pick the earliest possible inversion (i, j) (smallest i, then smallest j > i with a[i] > a[j]) and swap them.Repeat until the array is sorted.
...
- 11
1
vote
0
answers
81
views
What data structure minimizes the amount of combine operation in point updates and range queries (and having the smallest leading constant)?
Suppose you have an array $a$ of $n$ elements in an set $X$, and a associative binary operation $\circ \ \colon X \times X \rightarrow X$, that can be evaluated in constant time, but is costly (e.g. $...
- 13
0
votes
1
answer
82
views
Using Binary Indexed Trees to efficiently do range updates and range MINIMUM queries
It is already known that you can use two BITs (aka Fenwick Trees) to do RMQ in $O(logn)$ and point update in amortized $O(logn)$ time (Described in this paper.)
However, I want a step further, doing ...
- 13
0
votes
0
answers
49
views
Understanding Gabow's Microsets
I'm trying to understand Gabow's LCA algorithm in (static) trees with $O(n)$ time preprocessing and $O(1)$ time queries (this is different from the popular Euler tour + RMQ approach).
From what I ...
- 111
0
votes
0
answers
22
views
A wait-free consensus algorithm for three processes, with a swap object and the fetch-and-increment object together in one atomic step
We know that a swap object consists of a shared register and supports a swap operation
between the shared register and any local register, which atomically exchanges the
values of the two registers.
A ...
- 1
0
votes
1
answer
58
views
Can red-black tree augmentations depend on other augmentations and still be maintainable in O(logn)?
by "augmentation" i mean adding an additional field to each node.
All sources i found say something that falls into one of two categories:
"A field f in a red-black tree can be ...
- 3
1
vote
1
answer
71
views
Efficient merging of overlapping ranges with values preserving sum
Given a list of ranges each with an associated value, the metric at a point is the sum of the values of all overlapping ranges. The goal is to produce a list of non-overlapping ranges that preserve ...
- 11
0
votes
0
answers
76
views
What is the expected number of layers in a skip list?
Skip lists work in layers. My question is no more than that: What is the expected number of layers in a skip list with the parameter $p \in (0,1)$? My best attempt to so far is
$$\sum_{i = 1}^\infty i ...
- 60
0
votes
1
answer
59
views
Finding the top N elements from a subset of a Minkowski sum of two sets of disjoint time intervals that have minimal overlap with a given interval set
We have two sets A and B, where each element in A and B is a set of disjoint time intervals
We have a set C which is a subset of the Minkowski sum A + B, meaning:
For any a ∈ A and b ∈ B, if a + b ∈ ...
- 19
0
votes
1
answer
59
views
Skip List with each column having an integer instead of copying objects
I tried my best implementing a Skip List in C++ in which I had a particular idea that I wanted to try out. Instead having every element in the base level be a column vector, I only only have a singly-...
- 109
1
vote
1
answer
71
views
Changing what indicates the final node in a linked list
In a typical singly linked list, the final node is identified by setting its .next pointer to NULL:
If node.next == NULL, then node is the final node.
I'm considering an alternative test in which the ...
- 11