Amr Elmasry

activity

20102015

most citedStrengthened Lazy Heaps: Surpassing the Lower Bounds for Binary Heaps

1 citations · 1 across the 4 of their papers we have counts for

collaborators

4 papers

cs.DS2015

Counting Inversions Adaptively

Amr Elmasry

We give a simple and efficient algorithm for adaptively counting inversions in a sequence of $n$ integers. Our algorithm runs in $O (n + n l g (I n v / n))$ time in the word-RAM…

cs.DS2014★ 1 cited

Strengthened Lazy Heaps: Surpassing the Lower Bounds for Binary Heaps

Stefan Edelkamp, Jyrki Katajainen, Amr Elmasry

Let $n$ denote the number of elements currently in a data structure. An in-place heap is stored in the first $n$ locations of an array, uses $O (1)$ extra space, and supports the op…

cs.DS2014

Selection from read-only memory with limited workspace

Amr Elmasry, Daniel Dahl Juhl, Jyrki Katajainen +1

Given an unordered array of $N$ elements drawn from a totally ordered set and an integer $k$ in the range from $1$ to $N$ , in the classic selection problem the task is to find the…

cs.DS2010

Priority Queues with Multiple Time Fingers

Amr Elmasry, Arash Farzan, John Iacono

A priority queue is presented that supports the operations insert and find-min in worst-case constant time, and delete and delete-min on element x in worst-case O(lg(min{w_x, q_x}+…