Why the complexity of pop_heap is O(2 * log(N))?

Question

I saw in a several places that in priority_queue, the complexity of pop_heap is O(2 * log(N)), is that true? If yes, where that 2 come from? After removing first element it just needs to reconstruct heap, which would take O(log(N)).

Answer 1

why according to standard pop_heap may use 2logN comparisons, whereas push_heap only logN

To start with, remember heap has a structure of a binary tree, it means each node has at most two children (and obviously at most one parent).

How pop_heap works:

• Take top element. (O(1))
• Take last element and place it on the top. (O(1))
• Update heap using top -> bottom logic. You start from the top element and compare it with its two children. Switch current element with one of its children and proceed to the next level, or stop if current element is already in correct place (condition of the heap holds)

How push_heap works:

• Place element as the last element (leaf of the tree). (O(1))
• Update heap using bottom -> top logic. You start with element you just added, and compare it with its parent. Switch current element with its parent if necessary and proceed, or stop if condition of the heap holds already.

So, the main difference between two above operations is the logic of heap update (reconstruct). pop_heap uses top to bottom logic, and push_heap uses bottom to top logic. Both of them are of O(logN) complexity, since the whole structure is a binary tree. But pop_heap requires more comparisons because each time we need to compare current element with both 2 children. In the same time, during push_heap we need to compare current element only with its 1 (and only) parent.