2.4.1. Dynamic Heap

STL’s priority_queue is just a container adaptor, which cannot meet requirement in many cases. For example, priority_queue has no update, no erase methods, so we can it static heap. A dynamic heap is able to update and erase values. The following is a dynamic heap class implemented with STL’s heap function.

struct dynamic_heap {
    vector<int> d;
    dynamic_heap(const vector<int>& _d) {
        d = _d;
        make_heap(d.begin(), d.end());
    }
    void push(int i) {
        d.push_back(i); // O(LogN)
        push_heap(d.begin(), d.end());
    }
    int pop() {
        pop_heap(d.begin(), d.end()); // O(LogN)
        int t = d.back(); d.pop_back();
        return t;
    }
    void erase(int n) { // O(N)
        update(n, INT_MAX);
        pop();
    }
    void update(int old_, int new_) { // O(N+LogN) = O(N)
        int i = 0;
        for (; i < d.size(); ++i) // O(N)
            if (d[i] == old_) { d[i] = new_; break; }
        push_heap(d.begin(),d.begin()+i+1);// the same like sift up/down
    }
    int size() { return d.size(); }
};

With the built-in STL heap function, we can implement a dynamic heap class as above. It is pretty simple but the time complexity of update and erase are O(N). If we use a map to connect the data and index, we can reduce it to O(LogN). This data structure is called index heap. Index the data in the heap, so it takes O(1) time to find and O(LogN) to update and delete.