Can I read A Note on Constructing Binary Heaps with Periodic Networks on EtoBox?

A Note on Constructing Binary Heaps with Periodic Networks by Marek Piotrów is a Computer Science article available to read on EtoBox.

What is A Note on Constructing Binary Heaps with Periodic Networks about?

We consider the problem of constructing binary heaps on constant degree networks performing compare-exchange operations only. The heap data structure, introduced by William and Williams [Comm. ACM 7 (6) (1964) 347-348], has many applications and, therefore, has been intensively studied in sequential and parallel context. In particular, Brodal and Pinotti [Theoret. Comput. Sci. 250 (2001) [235][236][237][238][239][240][241][242][243][244][245] have recently presented two families of comparator networks: the first of depth 4 log N and the second of size O(N log log N) for constructing binary heaps of size N. In this note, we give an new construction of such a network with the running time improved to 3 log N. Moreover, the network has a novel property of being 3-periodic, that is, for each unit of time i the same sets of operations are performed in units i and i + 3. Then we argue that our construction is optimal with respect to the length of the period, that is, we prove that there is no 2-periodic network that is able to build a binary heap in sublinear time. Finally, we show that our construction can be used to decrease also the depth of the networks with O(N log log N) size.

Who reads A Note on Constructing Binary Heaps with Periodic Networks?

Author

Marek Piotrów

Publisher

Elsevier Science; Elsevier ; Elsevier BV (ISSN 0020-0190)

Published

2002

Language

EN

Field

Computer Science (Physical Sciences)