# Questions tagged [data-structures]

Questions about ways of storing data so that it can be used advantageously by algorithms.

1,650 questions
Filter by
Sorted by
Tagged with
3k views

### Is Group Theory useful in Computer Science in areas other than cryptography?

I have heard many times that Group Theory is highly important in Computer Science, but does it have any use other than cryptography? I tend to believe that it does have many other usages, but cannot ...
19 views

### How to map structured grid data onto a regular grid efficiently?

Context: First of all, my data: I am working with 3D data shaped onto a structured grid made of hexahedrons with for each 8 vertices and 12 edges. The data I'm working on is cell data (and not point ...
35 views

### What is the difference between python list and c++ vector?

I read about the similarities between the python list and c++ vector and it looks as if the only difference is python list is heterogeneous. Are there any other differences? How are they both ...
2k views

### Building heaps and heapsort using linked list

I know that linked list is not a appropriate data structure for building heaps but I am interested in knowing the time complexity of building heaps and heapsort using linked list. One of the answers ...
37 views

### Tight upper bound for forming an $n$ element Red-Black Tree from scratch

I learnt that in a order-statistic tree (augmented Red-Black Tree, in which each node $x$ contains an extra field denoting the number of nodes in the sub-tree rooted at $x$) finding the $i$ th order ...
45 views

### Efficiently storing and modifying a reorderable data structure in a database

I'm trying to create a list curation web app. One thing that's important to me is being able to drag-and-drop reorder items in the list easily. At first I thought I could just store the order of each ...
5k views

### how is data in a tree stored in memory?

I am not so familiar with trees. How is a tree stored in memory? what is the data structure type used for storing it? As a string?linked list? stack (!)? Or is there some kind of data storage model ...
54 views

### Disjoint Set Connected Components With Weighted Graph

I have been trying to solve this HackerRank problem (link). The basic premise of this problem is that there is a tree with undirected, but weighted, edges. The cost of a path in this tree is taken ...
46 views

### Uniform Hashing. Understanding space occupancy and choice of functions

I'm having troubles understanding two things from some notes about Uniform Hashing. Here's the copy-pasted part of the notes: Let us first argue by a counting argument why the uniformity property, we ...
32 views

### Augmenting AVL tree to calculate sum of subtree

Suggest a way to augment an AVL tree to support a $O(\log n)$ implementation of the function calculateSum(key), which receives a key of a node and returns the sum ...
54 views

### Is there a known way to make an efficient, compact, and fully persistent stack or queue?

In the world of mutable/ephemeral data structures and imperative programming languages, one of the classic ways to implement a stack or queue is to use array doubling: use mutation to fill up or empty ...
55 views

### Priority Queue - When Prioritizing Take Place?

In a Priority Queue we first enqueue according to the priority given to the element? Or we enqueue just like a queue but dequeue high the highest priority element first? Or both ways are acceptable?
14 views

### Maintaining balanced BSTs in order to get $\frac{n}{2}$ largest elements in constant time

I wonder what is the best data structure I can use in order to achieve the following: Given a data structure based on a balanced BST, I would like to get a tree with the $\lfloor\frac{n}{2}\rfloor$ ...
29 views

### Delete rows or columns of matrix containing invalid elements, such that a maximum number of valid elements is kept

Originally posted in Stack Overflow but was told to post here. Context: I am doing a PCA on a $M \times N \, (N \gg M)$ matrix with some invalid values located in the matrix. I cannot infer these ...
86 views

### Find number of triples that sum up to zero in query-intervals

My problem is that we have an array of $N$ integers $(N <=5000)$ on the interval $[-10^6,10^6]$. We also have $Q$ queries $(Q <= 10^5)$ giving us some range in the array. For each query, we ...
27 views

### Set data structure for data too large to fit into memory

I'm trying to solve the following exercise: Given N data items and memory that can hold M/B blocks of size B. Describe a data structure that needs at most N/B blocks of external memory and allows ...
10 views

### Method to change value in a key for a min heap

How would you write a method to change the value of a min heap where bool changeKey(int oldKey, int newKey). The keys are unique, no duplicate keys are permitted. If there is a key in the heap with ...
13 views

### Binomial trees in binomial heap with 27 elements

How many binomial trees are in a binomial heap with 27 elements and how would you find this number?
29 views

### Is the correct way to carry out a quick sort algorithm?

I have a question regarding the quicksort algorithm where the first element is the pivot. I'm still new at this and have been a little confused whether I'm going at this in the right direction. Is ...
30 views

### Use tree in-order traversal to determine whether a BST or Heap

Given these in-order traversal lists: 1. 53, 1, 64, 23, 3, 29, 17, 2, 9, 19 2. 49, 32, 51, 71, 32, 10, 21, 8, 13, 11, 41, 17 I need to determine whether each one of those lists represent a valid BST ...
55 views

### How do 2-3 FingerTrees generalize to bigger branching factors?

FingerTrees as implemented by Haskell's Data.Sequence use a branching factor of 2-3 for Nodes, and have Digits of size 1-4. Imagine we want to make the branching factor much wider -- perhaps to ...
45 views

### Implementing Queue operations in $\Theta(1)$

We want to implement a Queue which has two special operations besides the regular Queue operations: $getMiddle$(returns the element from the middle of the Queue, for example, if the Queue has 7 ...
83 views

### Formal definition of the Dynamic Array - what is the Dynamic Array

I've researched quite a bit about this topic. Since I'm kind of a fan of Exact Sciences, I love everything to have a crystal-clear and determined definition, without any ambiguous or dubious points. ...
50 views

### Data structure and structural relationships

“Computer programs usually operate on tables of information. In most cases these tables are not simply amorphous masses of numerical values, they involve important structural relationship between the ...
142 views

### How to delete an element from a B-tree

There is a lot of information online on this specific topic, but I still don't quite understand how to delete elements from a B-tree. For example, given the following tree, how would we delete 26 and ...
60 views

### Trees with duplicate nodes and path cancellations

I have a bunch of objects that I am not sure on how to represent in order to maximize memory occupancy and possibly avoiding large CPU overhead. The most natural way to see the whole data structure is ...
50 views

### Efficient Data Structure for Closest Euclidean Distance

The question is inspired by the following UVa problem: https://onlinejudge.org/index.php?option=onlinejudge&Itemid=99999999&category=18&page=show_problem&problem=1628. A network of ...
31 views

### How to estimate the number of elements inserted to a Bloom filter

A Bloom filter is a probabilistic data structure that allows encoding sets with false positives. Parameterized by the number of bits $m$ in the array $A$ (initialized to zeros), and number of hash ...
54 views

### How to represent sums of piecewise quadratic functions for efficient optimisation?

I'm trying to implement a decision procedure for finding solutions to a scheduling problem; this involves computing the point in time which is under the most contention. Each task to be scheduled has ...
696 views

### Algorithm for checking if all subarrays have an unique element

How to check if all subarrays of the array contain at least one unique element for NlogN complexity, where N is the length of the array? For example: 3 1 2 1 2 5 6...
289 views

### heap data structure complexity

I'm trying to count running time of build heap in heap sort algorithm ...
84 views

### Managing an hotel using AVL trees - Data Structures

I have a Data Structure question where I need to manage an hotel, each room has a number between $1-n$ and it can be occupied or not. Available Data structures: AVL* Trees, B-Trees, Arrays, Stacks, ...
11 views

### What is the insertion algorithm for an AVL tree with balance constraint of 2?

What would be the insertion algorithm for a modified AVL tree where the balance constraint is 2 instead of 1? Would be the same as a regular AVL tree?
74 views

### What does Lambda Calculus teach us about data?

In Lambda Calculus, the distinction between data and code doesn't seem to exist. Is there something fundamental about this, or purely Lambda Calculus's thing? Some context: as a software developer, I ...
53 views

### Name for type of actions that only care for outcome

There is a definition for kind of actions that only care for outcome. Classic example for such an action is remove from ...
26 views

### Finding minimal degree for a B-Tree

We are given 44,000,000 elements. We want to store them in a B-Tree so that his height is 5 (no more than 5). We are asked: "What is the minimal t we can choose?" ($t$ is the minimal degree, in ...
46 views

### Is there a way to get O(1) without extra space in the union find algorithm?

Is there a way to get O(1) without extra space in the union find algorithm? Imagine I have 3 sets set1 = {1, 3, 5, 7} set2 = {4,20,25} set3 = {9, 13} Now ...
25 views

### Enhance B-Tree with find(k) function

I have a question to enhance a B-Tree and add a function called find(k) which gets a key - k and returns the index of it in the sorted keys of the tree, using $O(N)$ space complexity, and it needs to ...
22 views