Creating a Self Ordering Binary Tree
Just two pointers:


If you want to actually combine the ideas of priority queues and binary search trees, think about combining heap and BST in one structure. 
There is the concept of self-organising lists. The idea is to move recently accessed element to (or towards the) front in order to speed up future accesses to the same element, thusly "learning" the element distribution over time (with quality depending on the particular implementation). Maybe you can adapt this to trees?




Spoiler: Follow below links only if you have not been able to come up with something yourself.


   1. This is called a treap.
 2. Splay trees implement this idea.