The author investigates the parallel complexity 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). The study is carried out by developing cost optimal parallel deterministic algorithms of time complexity Θ(log log n) and randomized algorithms of time complexity Θ(α(n)) with probability that converges rapidly to one on the parallel comparison tree model, where α(n) is the inverse Ackermann function. The author also describes constant-time parallel algorithms for the constructions with n1+∈ processors for any constant ∈>0 on the same model. Furthermore, the author designs optimal Θ(log n)-time EREW-PRAM algorithms for constructing double-ended priority queue structures