查看文章

A new priority queue is introduced, for which the cost to insert a new item is constant and the cost to delete the item x with the minimum value is O(log k_x), where k_x, is the number of items that are inserted after x and are still in the heap when x is deleted. We achieve the above bounds in both the amortized case and the worst case.