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.

.. code-block:: c++
  :linenos:

  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.