Priority data structure supporting operations Insert, Delete, Get in O(log n)

Question

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.

Answer 1

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.