O(log log N) time algorithms for Hamiltonian suffix and min-max-pair heap operations on the hypercube

This paper deals with a fast implementation of a heap data structure on a hypercube-connected, synchronous, distributed-memory multicomputer. In particular. we present a communication-efficient mapping of a min-max-pair heap on the hypercube architecture in which the load on each processor's local memory is balanced and propose cost-optimal parallel algorithms which require O((log N)/p + log p) time to perform single insertion, deletemin, and deletemax operations on a min-max-pair heap of size N, where p is the number of processors. Our imple mentation is based on an embedding of complete binary trees in the hypercube and an efficient parallel solution to a special kind of suffix computation, thai we call the Hamiltonian suffix, along a Hamiltonian path in the hypercube. The binary tree underlying the heap data structure is, however, not altered by the mapping process.