HEAPS WITH BITS

In this paper, we show how to improve the complexity of heap operation s and heapsort using extra bits. We first study the parallel complexit y of implementing priority queue operations on a heap. The trade-off b etween the number of extra bits used, the number of processors availab le, and the parallel time complexity is derived. While inserting a new element into a heap in parallel can be done as fast as parallel searc hing in a sorted list, we show how to delete the smallest element from a heap in constant time with a sublinear number of processors, and in sublogarithmic time with a sublogarithmic number of processors. The m odels of parallel computation used are the CREW PRAM and the CRCW PRAM . Our results improve those of previously known algorithms. Moreover, we study a variant, the fine-heap, of the traditional heap structure. A fast algorithm for constructing this new data structure is designed using an interesting technique, which is also used to develop an impro ved heapsort algorithm. Our variation of heapsort is faster than Wegen er's heapsort and requires less extra space.