We consider the problem of constructing data structures that implement priority queues (viz. the heap) and double-ended priority queues (namely, the twin-heap, the min-max heap, and the deap) quickly and optimally in parallel. Whereas all these heap-like structures can be built in linear sequential time, we show in this paper that the construction problem can be solved in O(log n·log* n/log log n) time using n·log log n/log n·log * n processors in the Arbitrary CRCW PRAM model. Moreover, by applying random sampling techniques, we reduce the construction time to O with probability ≥ 1-n-c for some constant c>0. As a by-product, we also investigate the parallel complexity of the multiple selection problem. The problem is to select a subset of elements having specified ranks from a given set. We design optimal solutions to the problem with respect to various models of parallel computation.