Geometric shapes are identified with their features. For computational purposes a concrete
mathematical definition of features is required. In this paper we use a topological approach …

Fredman, Sedgewick, Sleator and Tarjan proposed the pairing heap as a self-adjusting,
streamlined version of the Fibonacci heap. It provably supports all priority queue operations …

We give a variation of the pairing heaps for which the time bounds for all the operations
match the lower bound proved by Fredman for a family of similar self-adjusting heaps …

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 …

Quicksort was first introduced in 1961 by Hoare. Many variants have been developed, the
best of which are among the fastest generic-sorting algorithms available, as testified by the …

We give a variant of the pairing heaps that achieves the following amortized costs: O (1) per
find-min and insert, O (log log n) per decrease-key and meld, O (log n) per delete-min; …

We present two algorithms that are near optimal with respect to the number of inversions
present in the input. One of the algorithms is a variation of insertion sort, and the other is a …

A new adaptive sorting algorithm is introduced. The new implementation relies on using the
traditional AVL trees, and has the same performance limitations. More precisely, the number …

We study the performance of the most practical inversion-sensitive internal sorting
algorithms. Experimental results illustrate that adaptive AVL sort consumes the fewest …

We derive a variation of insertion sort that is near optimal with respect to the number of
inversions present in the input. The number of comparisons performed by our algorithms, on …