A heap whose levels alternate min and max, so both the smallest and the largest key are a step from the root, and both come out in O(log n).
This interactive visualization needs JavaScript.