Time Complexity of Differentiating Priority Queue Heap Via Key

Question

I have a priority queue max heap where each element is a class called Task, which looks as follows (implemented in Java, but question is language-agnostic):

class Task{

    int ID
    int Priority
    int Time

    public Task(int i, int p, int t){
        this.ID = i;
        this.Priority = p;
        this.Time = t;
    }

    //Getters, etc
}

The heap is obviously sorted by priority. The operation I want to perform is to find the highest priority item, decrement its Time value, and remove it from the heap if the time score changes to 0. HOWEVER, here's the catch: there is allowed to be more than one Task with the same Priority. In this case, I compare the ID scores of all such Tasks and operate on the lowest one.

What would be the worst case running time of such an operation? If every element has the same Priority, I would end up searching through the entire tree, meaning that this couldn't possibly be done in less than O(n) time, correct? This seems impossible to get around because the IDs are unsorted. However, I'm told that this is possible to do in O(log n), which I don't understand at all. Would anyone be able to clarify where I'm approaching this wrong?

the tags you've chosen don't have many followers, I suggest you use a language tag even if the question is language agnostic — 0x6C38

Kedar Mhaswade Kedar Mhaswade · Accepted Answer · 2017-07-02T02:38:41

A java.util.PriorityQueue (of Task instances) constructor can take a Comparator that can take into account the Task#Priority and Task#ID which means that the (priority) ties could be broken based on ID's which are (supposedly) unique. So, a Task t1(Priority=5, ID=100, Time=10) could precede (i.e. be prioritized over) a Task t2(Priority=5, ID=110, Time=10).

Removing such an item (which is at the root) that has highest priority along with others that may have the same priority, zero Time remaining and lowest ID is still an O(log(n)) operation in a heap or priority queue while maintaining the heap property. Note that priority queues are not great for searching (hash tables or binary search trees do that well); but for inserting or removing while maintaining the heap property. You should just work with the peek and remove API methods to achieve the operation you need while ensuring the time complexity (O(log n)) that the priority queue is designed for.

Time Complexity of Differentiating Priority Queue Heap Via Key

1 Answers