A binary search tree in which nodes have a randomly assigned priority. Updates keep priorities in heap order instead of keeping balance information and doing rebalance operations.