CODEWITHSUNDEEP
c++algorithmheap
cjlovering
cjlovering

Reputation: 57

Single 'Heapify' call when removing max and adding a new element c++ std::make_heap

Is it possible to pop the max, push a new element, and then call push_heap, maintaining the heap and only calling the bubble down algorithm once?

    // What I think is correct:
    heap.push_back(new_element);
    std::push_heap(heap.begin(), heap.end());
    std::pop_heap(heap.begin(), heap.end());
    heap.pop_back();

    // What I hope is correct:
    heap.pop_back();        
    heap.push_back(new_element);
    std::push_heap(heap.begin(), heap.end());

Is it 'safe' to remove the max and push a new element to a heap? I have tested it and it seems to be the case. Is there a reason I should not do this?

Very related question: How to change max element in a heap in C++ standard library?

Upvotes: 1

Views: 561

Answers (2)

jxh
jxh

Reputation: 70392

What you are asking for is nearly an exact duplicate of the linked question in your post body.

// Precondition is that v is already a heap.
int get_max_element_add_new (std::vector<int> &v, int value) {
    v.push_back(value);
    std::pop_heap(v.begin(), v.end());
    value = v.back();
    v.pop_back();
    return value;
}

Since pop_heap will swap the first and last values, the back will contain the max that you want to remove.

Upvotes: 1

AndyG
AndyG

Reputation: 41090

In a max heap created via make_heap, the maximum element will be on the front, and the appropriate way to remove it is with std::pop_heap, period.

A pop_front (not pop_back like you posit) would indeed remove the maximum element from the heap, but you are no longer guaranteed to have a heap. That is, popping the first element effectively moves the heaps left child into the root. If the right child was bigger, then the heap property is lost (and even if it worked for the first set of children, it may invalidate any subtree on account of the shift in the array).

Additionally, if you're using a contiguous container like a std::vector, then a pop_front (calling std::vector::erase on vector::begin) has the misfortune to cost you O(N) time, which is much worse than the O(log N) complexity of pop_heap.

The one scenario that you may (prematurely) optimize for is if you simply want to swap the maximum element with another element that is at least as big as the existing maximum element, or failing that, >= to the maximum element's largest child. In that case you may achieve O(1) complexity, but this is unlikely in the general case.

It's better to just have two O(log N) operations. The function grows so slowly that there will hardly be a difference between 1000 and 1 million element heaps.

Upvotes: 2

Related Questions