5
$\begingroup$

I need a queue $[x_0, ..., x_n]$ that supports the following operations:

  • $\operatorname{enqueue}([x_0, ..., x_n], x) = [x_0, ..., x_n, x]$
  • $\operatorname{dequeue}([x_0, ..., x_n]) = [x_1, ..., x_n]$
  • $\operatorname{lookup}([x_0, ..., x_n], i) = x_i$
  • $\operatorname{update}([x_0, ..., x_n], i, y) = [x_0, ..., x_{i - 1}, y, x_{i + 1}, ... x_n]$
  • $\operatorname{insert}([x_0, ..., x_n], i, y) = [x_0, ..., x_i, y, x_{i + 1}, ..., x_n]$
  • $\operatorname{delete}([x_0, ..., x_n], i) = [x_0, ..., x_{i - 1}, x_{i + 1}, ... x_n]$
  • $\operatorname{length}([x_0, ..., x_n]) = n + 1$

All operations should be in $O(\log n)$. The data structure should be atomic and persistent, i.e. it is written to a random-access data storage device, such a hard disk or flash memory. Therefore the data structure should minimize the number of seeks. I thought about using Counted B-Trees without keys and with a rollback journal. I also looked at several purely real-time functional data structures that use multiple lists (lists can be efficiently implemented with a file system with a truncate operation) but they seemed to be too complicated or not randomly accessible.

Assume that the filesystem has the following operations:

  • write(file, offset, x)
  • read(file, offset, length)
  • append(file, x)
  • truncate(file, length)

Is there any other data structure that I is more efficient or easier to implement while being as efficient?

$\endgroup$
1
  • $\begingroup$ What have you tried? Seems straightforward to achieve $O(\lg n)$ time for all operations with a balanced (binary) tree data structure, and there are many such data structures you could consider. What approaches have you considered, and why did you reject them? Is there a reason you are unhappy with a solution based on B-trees, or one of the B-trees variants? If you want to optimize for constant factors, that will probably depend on your specific workload, and thus is likely to be hard to answer given the limited information provided here. Also, the practical answer might be "use a SSD". $\endgroup$
    – D.W.
    Mar 22, 2016 at 1:45

1 Answer 1

2
$\begingroup$

Yes there is a data structure which name is Treap You can also do other things too (ex. range sum, range min-max, etc.) using this or you can also use BBST (Balanced binary search tree like AVL ).

Okay i will explain some terms i am assuming you have some Knowledge about Trees and BST(Binary search Tree)
Q. What Treap is?
A. Treap = Tree + Heap (in easy way)

Q. Use of Treap?
A. its randomized balanced tree basically its contain 2 values first one is data and second is rank (data, rank) and it has two property using data we keep BST(Binary search Tree) property it mean smaller than data will go on left side and bigger will be on right side and rank keep heap property its your choice that you want min heap aur max heap property. trick here is that rank is given uniformly random. So when we heapify using rank height of tree will not exceed O(LogN). so in easy implementation we can get a self balanced binary search tree.

Q. How to implement above requirements?
A. Insert and Delete methods are easy and equal to BST's methods

struct Node *insert(struct Node *root, int pos, int data) {
  if(root == dummy) {
    ptr ->left = ptr ->rig = dummy;
    ptr ->size = 1;
    ptr ->pri = rand();
    ptr ->data = data;
    return ptr++;
  } else if(root ->left ->size >= pos) {
    root ->left = insert(root ->left, pos, data);
    if(root ->left ->pri > root ->pri) root = rot(root, root ->left);
  } else {
    root ->rig = insert(root ->rig, pos - root ->left ->size - 1, data);
    if(root ->rig ->pri > root ->pri) root = rot(root, root ->rig);
  }
  update(root);
  return root;
}

here you can see 2 methods which are unknown to you actually one it rot which is rotation when our tree violate heap property and update where you can update your tree's attribute here we keeping size so you can updated this information here

Delete method is homework for you it will be same as insert in above code pos define that you want to insert an element in between pos-1 pos.

okay now lets come on your requirements :

enqueue -> call insert and pos will be root ->size
denqueue -> call delete 
lookup -> search method same as binary search tree's search method
update , insert -> call insert
length -> root ->size
$\endgroup$
1
  • $\begingroup$ Unfortunately, the data structure is neither atomic nor persistent (by the definition of the question). $\endgroup$ Jun 10, 2016 at 9:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.