When only the minimum (or maximum) is needed, a good approach is to use a heap, which is able to find the minimum (or maximum) element in constant time, while all other operations, including insertion, are O(log "n") or better. More generally, a self-balancing binary search tree can easily be augmented to make it possible to both insert an element and find the "k"th largest element in O(log "n") time; this is called an "order statistic tree." We simply store in each node a count of how many descendants it has, and use this to determine which path to follow. The information can be updated efficiently since adding a node only affects the counts of its O(log "n") ancestors, and tree rotations only affect the counts of the nodes involved in the rotation.