Deleting an Element From a 2 Heap database

Assume we got 2 diffrent Heaps - first heap is a min heap and second heap is a max heap ,together, they contain n diffrent elements, with not nessecerly diffrent keys, I need to delete element x, which has to be in one of the heaps but not in both of them as those heaps are diffrent.

The deletion needs to get done in complexity of O(logn).

NOTICE: heaps can have the keys in this order:

minHeap: 6,6,6,6,6,6

maxHeap: 6,6,4,3

to delete: x->开发者_如何学JAVAkey=6

How would you do that, is it possible to do that in the wanted complexity?

Hint: you may use HeapChangeKey which can change the key of element x to whatever you want - you can use it to bubble up the element you are searching for... (i had the solution if the heaps had no doubles, but no one tells me ahead that the keys are diffrent so the exemple above is why i need your help)

You can delete from a binary heap in O(log n) time by using the following algorithm:

1. Take the element to delete and use the bubble-up operation to swap it with its parent until it reaches the top of the heap.
2. Use the standard binary heap delete step to remove the top element of the heap and rebalance it.

This first step takes O(log n) time because you need to swap the element all the way to the top of the heap, which takes time proportional to the height of the heap (O(log n)) and the second step takes O(log n) as well. Thus if you can find the elements to delete out of each heap in O(log n) time, you can remove elements from the two heaps in O(log n) time.

One way to do this would be to augment the two heaps with hash tables or binary search trees mapping from the values in the heap to their positions. That way, when you need to delete an entry from one or both of the heaps, you can look in the hash table to find where in the binary heaps to look for the element and can then use the above procedure to remove the elements. You may need to update the code for heapifying the elements to update these tables as you move elements around.

Alternatively, if you don't need to store the elements in binary heaps, you could consider storing all the elements in balanced binary search trees. You can do all the standard priority queue operations on BSTs in O(log n) time, but can also easily delete elements from the BST-based priority queue in O(log n) time using a standard BST delete step.

Hope this helps!