A median heap is a priority queue that can access in constant time the median value of the content values.