How to convert a Complete Binary Tree to a Priority Search Tree in O(n) There doesn't seem to be any resources on this. 
I would like to know if there is a linear-time algorithm to convert a Complete Binary Tree with data left-to-right increasing stored in external nodes, to a Priority Search Tree.

edit: Convert = create a priority search tree with all of the elements of some complete binary tree

edit 2: or modify the original Complete Binary Tree such that it has all of the properties of a Priority Search Tree
No.  If you could, you'd obtain a sorting algorithm that would run in $O(n)$ time (construct the priority search tree, then traverse the nodes in increasing order of key), but you can't sort in $O(n)$ time.