A binary search tree in which nodes have another key, called the priority. Operations also keep the nodes heap ordered with regard to the priority.