A note on the height of thekth element in a heap

De Graaf and Kosters have studied the expected height of thekth element in a heap. They conjecture that, for largek, this is asymptotic to log₂ k + 0.72 .... We show that the height of thekth element is related to the depth of insertion in a digital search tree, and use this relation to prove their conjecture.This research was supported by grant FONDECYT (Chile) 91-1252.     

Improved bounds for the expected behaviour of AVL trees

In this paper we improve previous bounds on expected measures of AVL trees by using fringe analysis. A new way of handling larger tree collections that are not closed is presented. An inherent difficulty posed by the transformations necessary to keep the AVL tree balanced makes its analysis difficult when using fringe analysis methods. We derive a technique to cope with this difficulty obtaining the exact solution for fringe parameters even when unknown probabilities are involved. We show that the probability of a rotation in an insertion is between 0.37 and 0.73 (and seems to be less than 0.56), that the fraction of balanced nodes is between 0.56 and 0.78, and that the expected number of comparisons in a search seems to be at most 12% more than in the complete balanced tree.The work of the first author was also supported by the Institute for Computer Research of the University of Waterloo, the second author by a Natural Sciences and Engineering Research Council of Canada Grant No. A-3353, and the third by a Brazilian Coordenação do Aperfeiçoamento de Pessoal de Nível Superior Contract No. 4799/77 and by the University of Waterloo.     

Left distance binary tree representations

We present a new scheme for representing binary trees. The scheme is based on rotations as a previous scheme of Zerling. In our method the items of a representation have a natural geometric interpretation, and the algorithms related to the method are simple. We give an algorithm for enumerating all the representations for trees onn nodes, and an algorithm for building the tree corresponding to a given representation.This work was supported by the Academy of Finland.     

Page usage in a quadtree index

This paper provides a characterization of the storage needs of a quadtree when used as an index to access large volumes of 2-dimensional data. It is shown that the page occupancy for data in random order approaches 33%. A precise mathematical analysis that involves a modicum of hypergeometric functions and dilogarithms, together with some computer algebra is presented.A brief survey of the analysis of storage usage in tree structures is included. The 33% ratio for quadtrees is to be compared to the figures for binary search trees (50%), tries (69%), and quadtries (46%).The research of this author was done while visiting INRIA, Rocquencourt, France under support from the Ministry of Education of Japanese Government.Work of this author was supported in part by the Basic Research Action of the E.C. under contract No. 3075 (Project ALCOM).     

A note on constructing min-max heaps

In this paper we show that to construct an implicit, double-ended priority queue organized as a min-max heap, 17/9n = 1.88 ...n comparisons suffice in the worst case (neglectng lower order terms). The algorithm improves the previously best known upper bound of 2.15 ...n comparisons.Some of the ideas given in this paper were presented in a preliminary form at the 1st Scandinavian Workshop on Algorithm Theory, Halmstad (July, 1988) [7].     

Finding squares and rectangles in sets of points

A number of problems concerning sets of points in the plane are studied, e.g. establishing whether it contains a subset of size 4, which are the vertices of a square or rectangle. Both the problems of finding axis-parallel squares and rectangles, and arbitrarily oriented squares and rectangles are studied. Efficient algorithms are obtained for all of them. Furthermore, we investigate the generalizations tod-dimensional space, where the problem is to find hyperrectangles and hypercubes. Also, upper and lower bounds are given for combinatorial problems on the maxium number of subsets of size 4, of which the points are the vertices of a square or rectangle. Then we state an equivalence between the problem of finding rectangles, and the problem of findingK _{2, 2} subgraphs in bipartite graphs. Thus we immediately have an efficient algorithm for this graph problem.This work was partially supported by the ESPRIT Basic Research Action No. 3075 (project ALCOM). Work of the second author was also supported by the Dutch Organisation for Scientific Research (N.W.O.).     

On-line sorting of twisted sequences in linear time

A sequence of real numbers is called twisted if it can be produced from the sorted sequence by repeatedly reversing the order of consecutive subsequences. It is shown that twisted sequences constitute a class of exponentially many members each of which can be recognized and sorted, by a simple on-line algorithm, in linear time.Research was supported by the Austrian Fonds zur Förderung der Wissenschaftlichen Forschung.     

A select and insert sorting algorithm

A general sorting algorithm, having the well knownO(n ²) algorithmsStraight Insertion Sort andSelection Sort as special cases, is described. This algorithm is analyzed in the case that certain choices in the algorithm are done randomly, and this yields an algorithm that has an average complexity ofO(n ^1.5) and a worst case complexity ofO(n ²). However, making random choices (by some random number generator) is time consuming, and a simple quasi-random scheme is therefore implemented. Test runs indicate that also this version has average complexity ofO(n ^1.5), and it even seems to perform better than the version using real random choices (even if we disregard the time used for the random choices). This version also needs very little administrative overhead, and it therefore compares favourably to many other sorting algorithms for small and medium sized arrays.     

A parallel derangement generation algorithm

A parallel algorithm to generate allD _n derangements ofn distinct elements is presented in this paper. The algorithm requiresO([D _n /P]nlogn) time whenP processors are available on a Single Instruction Multiple Data Stream (SIMD) computer.     

Generating alternating permutations lexicographically

A permutation _{1 2} ... _n is alternating if ₁<₂>₃<₄ .... We present a constant average-time algorithm for generating all alternating permutations in lexicographic order. Ranking and unranking algorithms are also derived.Research supported by the Natural Sciences and Engineering Research Council of Canada under grant A3379.     

A maximum stable matching for the roommates problem

The stable roommates problem is that of matchingn people inton/2 disjoint pairs so that no two persons, who are not paired together, both prefer each other to their respective mates under the matching. Such a matching is called a complete stable matching. It is known that a complete stable matching may not exist. Irving proposed anO(n ²) algorithm that would find one complete stable matching if there is one, or would report that none exists. Since there may not exist any complete stable matching, it is natural to consider the problem of finding a maximum stable matching, i.e., a maximum number of disjoint pairs of persons such that these pairs are stable among themselves. In this paper, we present anO(n ²) algorithm, which is a modified version of Irving's algorithm, that finds a maximum stable matching.This research was supported by National Science Council of Republic of China under grant NSC 79-0408-E009-04.     

Arranging apples in an array

Departing from a real-world problem we consider a greedy algorithm which either finds a 0–1 matrix with prescribed row and column sums or terminates with the conclusion that no such matrix exists.The problem has been pending in the literature for about 30 years. Our proof of the validity of the algorithm is established along with an account of earlier findings and appears to be considerably simpler than any other proof hitherto proposed. Various open questions conclude the paper.Dedicated to Peter Naur on the occasion of his 60th birthday     

Minimal perfect hashing in polynomial time

We present a universally applicable algorithm for generating minimal perfect hashing functions. The method has (worst case) polynomial time complexity in units of bit operations. An adjunct algorithm for reducing parameter magnitudes in the generated hash functions is given. This probabilistic method makes hash function parameter magnitudes independent of argument (input key) magnitudes.     

A linear time and space algorithm for finding isomorphic subtrees of a binary tree

This paper shows that it is possible to find all isomorphic subtrees of a binary tree in linear time and space.     

A generalized hypergreedy algorithm for weighted perfect matching

We give a generalization of the hypergreedy algorithm for minimum weight perfect matching on a complete edge weighted graph whose weights satisfy the triangle inequality. With a modified version of this algorithm we obtain a logn-approximate perfect matching heuristic for points in the Euclidean plane, inO(n log² n) time.This research was supported in part by the DIMACS Grant No. NSF-STC88-09648.This research was supported in part by the NSF under Grant No. CCR 88-07518.     

Average search and update costs in skip lists

Skip lists, introduced by Pugh, provide an alternative to search trees, although a precise analysis of their behaviour had been elusive. The exact value of the expected cost for the search of themth element in a skip list ofn elements is derived first in terms of previously studied functions, and secondly as an asymptotic expression. The latter suggests that Pugh's upper bound of the expected search cost is fairly tight for the interesting cases. Assuming a uniform query distribution, the exact and an asymptotic value of the average (over allm) expected search cost in a skip list ofn elements is also derived. Finally, all insert and delete costs are obtained.This research was supported in part by the Natural Science and Engineering Research Council of Canada under grant No. A-8237, the Information Technology Research Centre of Ontario, and FON-DECYT (Chile) under grant 91-1252.     

A dual approach to detect polyhedral intersections in arbitrary dimensions

This paper presents a dual approach to detect intersections of hyperplanes and convex polyhedra in arbitrary dimensions. Ind dimensions, the time complexities of the dual algorithms areO(2 ^d logn) for the hyperplane-polyhedron intersection problem, andO((2d) ^d–1 log ^d–1 n) for the polyhedron- polyhedron intersection problem. These results are the first of their kind ford > 3. In two dimensions, these time bounds are achieved with linear space and preprocessing. In three dimensions, the hyperplane-polyhedron intersection problem is also solved with linear space and preprocessing; quadratic space and preprocessing, however, is required for the polyhedron-polyhedron intersection problem. For generald, the dual algorithms require space and preprocessing. All of these results readily extend to unbounded polyhedra.This is an extended and revised version of a paper presented at the 25th Annual Allerton Conference on Communication, Control, and Computing (October 1987). Our work was sponsored by the U.S. Army Research Office (research contract DAAG29-85-0223) and, in the case of the first author, by graduate fellowships from the IBM corporation and the German National Scholarship Foundation.     

Computing parent nodes in threaded binary trees

We give three algorithms for computing the parent of a node in a threaded binary tree, and calculate the average case complexity of each. By comparing these to the unit cost of obtaining the parent of a node with an explicit parent-pointer field, it is possible to balance runtime and storage cost with respect to the task of finding parent nodes in binary trees. The results obtained show that, although the worst case complexity for ann-node tree is obviouslyO(n) for all three algorithms, the average case complexity for two input distributions is asymptotic (from below) to either 3 or 2.     

Searchability in merging and implicit data structures

We introduce the notion ofsearchability as a property of an in place merging algorithm. We show that a pair of sorted arrays can be merged in place in linear time, so that a search can be performed in logarithmic time at any point during the merging process. We apply this method to devise an implicit data structure which can support searches inO(log² n) time in the worst case, andO(logn) on the average, and insertions inO(logn) time, in the worst case.This research was partly supported by NSERC under grant A8237 and presented in preliminary form at the 10th International Colloquium on Automata, Languages and Programming.On leave from the University of Chile.     

Counting labels in binary trees

We investigate properties of binary (search) trees related to the inorder labelling of the nodes. Both permutation and uniform trees are considered. We give explicit formulas to count the number of interior, middle and final nodes (leaves) containing a specific label. Possible applications are discussed.This work was supported by the Italian Ministry for Public Education.