Finding an Item in a Heap

Let’s see what changePriority takes on the binary heap. Suppose the queue holds these patients, stored in the heap’s array by priority:

         ┌─────┬─────┬─────┬─────┬─────┐
 index   │   0 │   1 │   2 │   3 │   4 │
         ├─────┼─────┼─────┼─────┼─────┤
 item    │ Amy │ Bob │ Cal │ Dan │ Eve │
         ├─────┼─────┼─────┼─────┼─────┤
 prio    │   1 │   2 │   4 │   5 │   3 │
         └─────┴─────┴─────┴─────┴─────┘

Amy at priority 1 is the root, and every parent is at least as urgent as its children.

Now Dan’s condition worsens to the most urgent level, so we call changePriority(Dan, 1). The queue has to do three things: find where Dan sits in the array, change his priority to 1, and move him to his new place so the heap is valid again.

The last two are cheap and familiar. Changing the stored priority is one assignment. Moving Dan to his new place is a swim or a sink, which the priority queue chapter showed costs $O (lo g n)$ . The costly part is the first step: finding Dan.

We have no direct way to know where Dan is in the array, so we have to do a linear search. A sorted array can be binary-searched in $O (lo g n)$ , but the heap’s array is not sorted, not by patient and not even fully by priority.

So on the plain heap, changePriority is $O (n)$ to find the patient plus $O (lo g n)$ to move him, which is $O (n)$ in total. contains has the same problem, because it too has to find the item, so it is $O (n)$ as well.

An $O (n)$ changePriority defeats the point of using a heap. For this operation, the heap is no better than the flat structures from the priority queue chapter.