I need a data structure to store priority $p$ for each key $k$ (unique). It must also support the following operations in $O(\log n)$ time:
$\text{Insert}(k,p)$ Inserts a key $k$ with priority $p$ into the structure. If there already is an element with key $k$, it changes its priority instead.
$\text{Delete}(k)$ Delete the element with key $k$.
$\text{Get}(k)$ Return the element with least priority among all elements with key $k' \leq k$.
At first I thought about balanced binary search trees. However I'd need to sort the elements by key and that just ruins the time complexity of the $\text{Get}$ operation.
Having two trees where one is sorted by key and the second one by priority doesn't help either.
Then I thought about using Fibonacci Heap, but here I have exactly the same problem.