Heapify in logarithmic time using the C++ standard library

Question

I have a heap using std::make_heap:

std::vector<int> v{1,2,3,5,9,20,3};
std::make_heap(v.begin(), v.end());

now I update the heap by changing one random element:

v[3] = 35;

Is there a way in standard library in to adjust heap again in O(log n) time where n is size of container. Basically I am looking for heapify function. I know what element has been changed.

I understand that std::make_heap is O(n log n) time. I have also gone through duplicate question but that is different in sense that it is changing max element. For that solution is already given of O(log n) complexity in that question.

I am trying to change any random element within heap.

Answer 1

You can just do it yourself:

void modify_heap_element(std::vector<int> &heap, size_t index, int value)
{
    //while value is too large for its position, bubble up
    while(index > 0 && heap[(index-1)>>1] < value)
    {
        size_t parent = (index-1)>>1;
        heap[index]=heap[parent];
        index = parent;
    }
    //while value is too large for its position sift down
    for (;;)
    {
        size_t left=index*2+1;
        size_t right=left+1;
        if (left >= heap.size())
            break;
        size_t bigchild = (right >= heap.size() || heap[right] < heap[left] ?
                           left : right );
        if (!(value < heap[bigchild]))
           break;
        heap[index]=heap[bigchild];
        index = bigchild;
    }
    heap[index] = value;
}

Answer 2

If we look closer at your statement:

now I disturb heap by changing one random element of heap.

For heapifying in O(log n) you can only directly "disturb" the back or the front of the vector (which corresponds somehow to inserting or deleting an element). In these cases, (re)heapification can be then achieved by means of the std::push_heap and std::pop_heap algorithms, which take logarithmic running time.

That is, the back:

v.back() = 35;
std::push_heap(v.begin(), v.end()); // heapify in O(log n)

or the front:

v.front() = 35;

// places the front at the back
std::pop_heap(v.begin(), v.end()); // O(log n)
// v.back() is now 35, but it does not belong to the heap anymore

// make the back belong to the heap again
std::push_heap(v.begin(), v.end()); // O(log n)

Otherwise you need to reheapify the whole vector with std::make_heap, which takes linear running time.

---

Summary

It's not possible to modify an arbitrary element of the heap and achieve the heapification in logarithmic running time with the standard library (i.e., the function templates std::push_heap and std::pop_heap). However, you can always implement the heap's swim and sink operations by yourself in order to heapify in logarithmic running time.