Priority data structure supporting operations Insert, Delete, Get in O(log n)
Store the items in a balanced binary tree, sorted by key.  Augment each node of the binary tree to have a pointer to the lowest-priority element within the subtree rooted at that node.  This allows you to implement all three operations in $O(\log n)$ time.

Details: Whenever you insert or delete an element, you can follow the path from that element to the root, updating the augmented data inside each node you visit as you go.  This enables you to implement Insert and Delete in $O(\log n)$ time.  Any interval of keys can be expressed as the union of $O(\log n)$ subtrees, so the Get operation only needs to examine the augmented data inside $O(\log n)$ nodes and thus can be implemented in $O(\log n)$ time.