在Java的PriorityQueue中,有remove这一个函数,可以删除指定的元素。此时的时间复杂度为O(n),因为在删除之前得先遍历一遍数组,找到该元素。

但是如果对这个操作的调用比较频繁,那么我们就可以对这个函数进行改进,即用一个Hash Table存储每个元素的数组的下标,这样,删除元素时,我们不用遍历数组来找到该元素的位置,直接删除即可,时间复杂度为O(logn)。

应用见

http://www.lintcode.com/en/problem/building-outline/