Asymptotically efficient in-place merging (2009)
Geffert, Viliam, Katajainen, Jyrki, Pasanen, Tomi
http://www.tucs.fi/Publications/journals/jGeKaPaa.php
Claus Jensen, Jyrki Katajainen
We introduce a framework for reducing the number of element comparisons performed in priorityqueue operations. In particular, we give a priority queue which guarantees the worst-case cost of O(1) per...
Making operations on standard-library containers strongly exception safe (2008)
Abstract. An operation on an element container is said to provide a strong guarantee of exception safety if, in case an exception is thrown, the operation leaves the container in the state in which...
Relatore Prof, Paolo Massazza, Correlatore Prof, Jyrki Katajainen, Anno Accademico, Candidato Fabio Vitale
An investigation into efficient
Amr Elmasry, Claus Jensen Jyrki, Amr Elmasry, Claus Jensen, Jyrki Katajainen
Two-tier relaxed heaps
Abstract On the Power of Structural Violations in Priority Queues (2008)
Amr Elmasry, Claus Jensen, Jyrki Katajainen
We give a priority queue that guarantees the worstcase cost of Θ(1) per minimum finding, insertion, and decrease; and the worst-case cost of Θ(lg n) with at most lg n + O ( √ lg n) element...
Abstract Space-Efficient Planar Convex Hull Algorithms 1 (2008)
Hervé Brönnimann, John Iacono, Jyrki Katajainen, Pat Morin, Jason Morrison, Godfried Toussaint
A space-efficient algorithm is one in which the output is given in the same location as the input and only a small amount of additional memory is used by the algorithm. We describe four...
Experimental evaluation of local heaps (2008)
Claus Jensen, Jyrki Katajainen, Fabio Vitale
Abstract. In this paper we present a cache-aware realization of a priority queue, named a local heap, which is a slight modification of a standard binary heap. The new data structure is cache...
Generic Algorithm for 0/1-Sorting (2008)
Gianni Franceschini, Jyrki Katajainen
Abstract. In the 0/1-sorting problem, given a sequence S of elements drawn from a universe E and a characteristic function f: E → {0, 1}, the task is to rearrange the elements in S so that every...
Generic Algorithm for 0/1-Sorting (2008)
Gianni Franceschini, Jyrki Katajainen
Abstract. In the 0/1-sorting problem, given a sequence S of elements drawn from a universe E and a characteristic function f: E → {0, 1}, the task is to rearrange the elements in S so that every...
An extended truth about heaps ⋆ (2008)
Claus Jensen, Jyrki Katajainen, Fabio Vitale
Abstract. We describe a number of alternative implementations for the heap functions, which are part of the C++ standard library, and provide a through experimental evaluation of their performance....
In Turku Finland, Jyrki Katajainen, Tomi Pasanen, Jyrki Katajainen
A randomized in-place algorithm for positioning the kth element in a multiset Authors:
Experimental evaluation of local heaps (2008)
Claus Jensen, Jyrki Katajainen, Fabio Vitale
Abstract. In this paper we present a cache-aware realization of a priority queue, named a local heap, which is a slight modification of a standard binary heap. The new data structure is cache...
Instructions to use DIKU style files (2008)
Abstract. Each report must include an abstract that summarizes the results. Recommended length is at most 150 words. The abstract should not contain any references or displayed equations. L...
Instructions to use DIKU style files (2008)
Abstract. Each report must include an abstract that summarizes the results. Recommended length is at most 150 words. The abstract should not contain any references or displayed equations. L...
Abstract On the Power of Structural Violations in Priority Queues (2008)
Amr Elmasry, Claus Jensen, Jyrki Katajainen
We give a priority queue that guarantees the worstcase cost of Θ(1) per minimum finding, insertion, and decrease; and the worst-case cost of Θ(lg n) with at most lg n + O ( √ lg n) element...
Abstract On the Power of Structural Violations in Priority Queues (2008)
Amr Elmasry, Claus Jensen, Jyrki Katajainen
We give a priority queue that guarantees the worstcase cost of Θ(1) per minimum finding, insertion, and decrease; and the worst-case cost of Θ(lg n) with at most lg n + O ( √ lg n) element...
Jyrki Katajainen, Fabio Vitale
Abstract. A data structure, named a navigation pile, is described and exploited in the implementation of a sorting algorithm, a priority queue, and a priority deque. When carrying out these tasks, a...
Multipartite Priority Queues (2008)
Elmasry, Amr, Jensen, Claus, Katajainen, Jyrki
We introduce a framework for reducing the number of element comparisons performed in priority-queue operations. In particular, we give a priority queue which guarantees the worst-case cost of $O(1)$...
Nordic Journal of Computing PRACTICAL IN-PLACE MERGESORT (2007)
Jyrki Katajainen, Tomi Pasanen, Jukka Teuhola
Abstract. Two in-place variants of the classical mergesort algorithm are analysed in detail. The first, straightforward variant performs at most N log 2 N + O(N) comparisons and 3N log 2 N + O(N)...
Jyrki Katajainen, Tomi Pasanen
Abstract. We consider the problem of sorting a multiset of size n containing m distinct elements, where the ith distinct element appears n i times. Under the assumption that our model of computation...
Jyrki Katajainen, Tomi Pasanen
In the stable 0-1 sorting problem the task is to sort an array of n elements with two distinct values such that equal elements retain their relative input order. Recently, Munro, Raman and Salowe...
In-Place Planar Convex Hull Algorithms (2007)
Hervé Brönnimann, John Iacono, Jyrki Katajainen, Pat Morin, Jason Morrison, Godfried Toussaint
An in-place algorithm is one in which the output is given in the same location as the input and only a small amount of additional memory is used by the algorithm. In this paper we describe three...
Space-Efficient Planar Convex Hull Algorithms (2007)
Hervé Brönnimann, John Iacono, Jyrki Katajainen, Pat Morin, Jason Morrison, Godfried Toussaint
A space-efficient algorithm is one in which the output is given in the same location as the input and only a small amount of additional memory is used by the algorithm. We describe four...
Abstract. The Standard Template Library (STL) is a collection of generic algorithms and data structures that is part of the standard run-time environment of the C++ programming language. The STL...
Abstract. The Standard Template Library (STL) is a collection of generic algorithms and data structures that is part of the standard run-time environment of the C++ programming language. The STL...
Putting your data structure on a diet (2007)
Hervé Brönnimann, Jyrki Katajainen, Pat Morin
Abstract. Consider a data structure D that stores a dynamic collection of elements. Assume that D uses a linear number of words in addition to the elements stored. In this paper several...
Putting your data structure on a diet (2007)
Hervé Brönnimann, Jyrki Katajainen, Pat Morin
Abstract. Consider a data structure D that stores a dynamic collection of elements. Assume that D uses a linear number of words in addition to the elements stored. In this paper several...
Compressing spatio-temporal trajectories. Submitted (2007)
Joachim Gudmundsson, Jyrki Katajainen, Damian Merrick, Cahya Ong
Abstract. Trajectory data is becoming increasingly available and the size of the trajectories is getting larger. In this paper we study the problem of compressing spatio-temporal trajectories such...
Jyrki Katajainen, Gerth Stølting Brodal, Hervé Brönnimann, Manuel Macías Córdoba, Miguel Fiandor Gutiérrez, Kasper Egdø, ...
This volume contains the papers presented at the 6th STL Workshop which was
Amr Elmasry, Claus Jensen, Jyrki Katajainen
Abstract. We introduce an adaptation of run-relaxed heaps which provides efficient heap operations with respect to the number of element comparisons performed. Our data structure guarantees the...
Two new methods for transforming priority queues into double-ended priority queues (2006)
Amr Elmasry, Claus Jensen, Jyrki Katajainen
Abstract. Two new ways of transforming a priority queue into a double-ended priority queue are introduced. These methods can be used to improve all known bounds for the comparison complexity of...
Amr Elmasry, Claus Jensen, Jyrki Katajainen
Abstract. We introduce an adaptation of run-relaxed heaps which provides efficient heap operations with respect to the number of element comparisons performed. Our data structure guarantees the...
An experimental evaluation of navigation piles (2006)
Claus Jensen, Jyrki Katajainen
Abstract. A navigation pile, which can be used as a priority queue, is an extension of a selection tree. In a compact form the whole data structure requires only a linear number of bits in addition...
Project proposal: A meldable, iterator-valid priority queue, CPH (2005)
Abstract. The Standard Template Library (STL) is a library of generic algorithms and data structures that has been incorporated in the C++ standard and ships with all modern C++ compilers. In the CPH...
Relaxed weak queues: an alternative to run-relaxed heaps (2005)
Amr Elmasry, Claus Jensen, Jyrki Katajainen
Abstract. A simplification of a run-relaxed heap, called a relaxed weak queue, is presented. This new priority-queue implementation supports all operations as efficiently as the original: find-min,...
Relaxed weak queues: an alternative to run-relaxed heaps (2005)
Amr Elmasry, Claus Jensen, Jyrki Katajainen
Abstract. A simplification of a run-relaxed heap, called a relaxed weak queue, is presented. This new priority-queue implementation supports all operations as efficiently as the original: find-min,...
Project proposal: A meldable, iterator-valid priority queue, CPH (2005)
Abstract. The Standard Template Library (STL) is a library of generic algorithms and data structures that has been incorporated in the C++ standard and ships with all modern C++ compilers. In the CPH...
Brodal, Gerth Stølting, Fagerberg, Rolf, Meyer, Ulrich, Zeh, Norbert, Hagerup, Torben, Katajainen, Jyrki
A framework for speeding up priorityqueue operations (2004)
Amr Elmasry, Claus Jensen, Jyrki Katajainen
Abstract. We introduce a framework for reducing the number of element comparisons performed in priority-queue operations. In particular, we give a priority queue which guarantees the worst-case cost...
Brodal, Gerth Stølting, Fagerberg, Rolf, Meyer, Ulrich, Zeh, Norbert, Hagerup, Torben, Katajainen, Jyrki
Space-efficient planar convex hull algorithms (2002)
Herve Brönnimann, John Iacono, Jyrki Katajainen, Pat Morin, Jason Morrison, Godfried Toussaint
A space-efficient algorithm is one in which the output is given in the same location as the input and only a small amount of additional memory is used by the algorithm. We describe four...
Optimal in-place planar convex hull algorithms (2002)
Hervé Brönnimann, John Iacono, Jyrki Katajainen, Pat Morin, Godfried Toussaint
An in-place algorithm is one in which the output is given in the same location as the input and only a small amount of additional memory is used by the algorithm. In this paper we describe three...
Experiences with the design and implementation of space-efficient deques (2001)
Jyrki Katajainen, Bjarke Buur Mortensen
Abstract. A new realization of a space-efficient deque is presented. The data structure is constructed from three singly resizable arrays, each of which is a blockwiseallocated pile (a heap without...
Experiences with the design and implementation of space-efficient deques (2001)
Jyrki Katajainen, Bjarke Buur Mortensen
Abstract. A new realization of a space-efficient deque is presented. The data structure is constructed from three singly resizable arrays, each of which is a blockwiseallocated pile (a heap without...
Asymptotically efficient in-place merging (2000)
Viliam Geffert, Jyrki Katajainen, Tomi Pasanen
Two linear-time algorithms for in-place merging are presented. Both algorithms perform at most m(t+1)+n=2 t +o(m) comparisons, where m and n are the sizes of the input sequences, m n, and t = blog 2...
Introduction to Algorithmics Exercise O1, Spring 2000 Jyrki Katajainen Department of Computing, University of Copenhagen DK-2100 Copenhagen East, Denmark E-mail: jyrki@diku.dk This exercise consists...
In-Place Sorting with Fewer Moves (1999)
Katajainen, Jyrki, Pasanen, Tomi
http://www.tucs.fi/Publications/journals/jKaPa99a.php
Heaps and Heapsort on Secondary Storage (1999)
Fadel, Ramzi, Jakobsen, Kim Vagn, Katajainen, Jyrki, Teuhola, Jukka
In-place sorting with fewer moves (1999)
Jyrki Katajainen, Tomi A. Pasanen
It is shown that an array of n elements can be sorted using O(1) extra space, O(n log n = log log n) element moves, and n log 2 n+O(n log log n) comparisons. This is the first in-place sorting...
Performance Engineering Case Study: Heap Construction (1999)
Jesper Bojesen, Jyrki Katajainen, Maz Spork
this paper we study, both analytically and experimentally, the performance of programs that construct a binary heap [Williams 1964] in a hierarchical memory system. Especially, we consider the...
Worst-case efficient external-memory priority queues (1998)
Gerth Stlting Brodal, Jyrki Katajainen
Abstract. A priority queue Q is a data structure that maintains a collection of elements, each element having an associated priority drawn from a totally ordered universe, under the operations...
. A variant of Heapsort---named Ultimate Heapsort---is presented that sorts n elements in-place in \Theta(n log 2 (n+ 1)) worst-case time by performing at most n log 2 n + \Theta(n) key comparisons...
In-Place Sorting With Fewer Moves (1998)
Jyrki Katajainen, Tomi A. Pasanen
. It is shown that an array of n elements can be sorted using O(1) extra space, O(n log n= log log n) element moves, and n log 2 n+O(n log log n) comparisons. This is the first in-place sorting...
Worst-Case Efficient External-Memory Priority Queues (1998)
Gerth St, Gerth St��lting Brodal, Im Stadtwald, Jyrki Katajainen
A priority queue Q is a data structure that maintains a collection of elements, each element having an associated priority drawn from a totally ordered universe, under the operations Insert, which...
Torben Hagerup, Naomi Nishimura, Jyrki Katajainen, Prabhakar Ragde
We show that if a flow network has k input/output terminals (for the traditional maximum-flow problem, k = 2), its external flow pattern (the possible values of flow into and out of the terminals)...
Asymptotically Efficient In-Place Merging (1997)
Geffert, Viliam, Katajainen, Jyrki, Pasanen, Tomi
http://www.tucs.fi/Publications/techreports/TR148.php
External heaps combined with effective buffering (1997)
Fadel, R., Jakobsen, K. V., Katajainen, Jyrki, Teuhola, Jukka
Worst-Case Efficient External-Memory Priority Queues (1997)
Gerth Stølting Brodal, Gerth St��lting Brodal, Im Stadtwald, Jyrki Katajainen
A priority queue Q is a data structure that maintains a collection of elements, each element having an associated priority drawn from a totally ordered universe, under the operations Insert, which...
A meticulous analysis of mergesort programs (1997)
Jyrki Katajainen, Jesper Larsson Trgff
Abstract. The efficiency of mergesort programs is analysed under a simple unit-cost model. In our analysis the time performance of the sorting programs includes the costs of key comparisons, element...
Practical in-place mergesort (1996)
Katajainen, Jyrki, Pasanen, Tomi, Teuhola, Jukka
http://www.tucs.fi/Publications/journals/jKaPaTe96.php
Asymptotically efficient in-place merging (1995)
Katajainen, Jyrki, Pasanen, Tomi, Titan, George
http://www.tucs.fi/Publications/proceedings/pKaPaTi95a.php
Characterizations of k-Terminal Flow Networks and Computing Network Flows in Partial k-Trees (1995)
Torben Hagerup, Naomi Nishimura, Jyrki Katajainen, Prabhakar Ragde
We show that if a flow network has k input/output terminals (for the traditional maximum-flow problem, k = 2), its external flow pattern (possible values of flow at the terminals) has two...
A fast and space-economical algorithm for length-limited coding (1995)
Jyrki Katajainen, Alistair Moffat, Andrew Turpin
Abstract. The minimum-redundancy prefix code problem is to determine a list of integer codeword lengths I = [li l i E {1... n}], given a list of n symbol weightsp = [pili C {1.n}], such that ~'...
Sorting multiset stably in minimum space (1994)
Katajainen, Jyrki, Pasanen, Tomi
http://www.tucs.fi/Publications/journals/jKaPa94a.php
Jyrki Katajainen, Erkki Mäkinen
Different methods for compressing trees are surveyed and developed. Tree compression can be seen as a trade-off problem between time and space in which we can choose different strategies depending on...
Bucketing and filtering in computational geometry /--by Jyrki Katajainen. (1987)
Thesis (doctoral)--University of Turku, 1987.