Line data    Source code

       1             : #pragma once
       2             : 
       3             : #include <vector>
       4             : 
       5             : #include "Alg/PriorityQueue.hpp"
       6             : 
       7             : namespace Alg {
       8             : template<class T>
       9             : /**
      10             :  * @brief Binary heap.
      11             :  */
      12          19 : class BinaryHeap: public PriorityQueue<T> {
      13             :     class BinHeapElement: public PriorityQueue<T>::Element {
      14             :         friend BinaryHeap;
      15             : 
      16             :        private:
      17             :         BinaryHeap &binaryHeap;
      18             :         size_t      index;
      19             :         T           value;
      20       14790 :         BinHeapElement(BinaryHeap &heap, size_t i, T t):
      21       14790 :             binaryHeap(heap), index(i), value(t) {}
      22             : 
      23             :        public:
      24      433025 :         virtual T getValue() { return value; }
      25             : 
      26         152 :         virtual void decreaseKey(T t) {
      27         152 :             value = t;
      28         152 :             binaryHeap.heapifyDown(index);
      29         152 :         }
      30             : 
      31             :        private:
      32      122580 :         static void swap(BinHeapElement *&e1, BinHeapElement *&e2) {
      33      122580 :             std::swap(e1->index, e2->index);
      34      122580 :             std::swap(e1, e2);
      35             :         }
      36             :     };
      37             : 
      38             :     typedef std::vector<BinHeapElement *> Container;
      39             : 
      40             :     Container container = Container(1, nullptr);
      41             : 
      42             :    public:
      43          24 :     ~BinaryHeap() {
      44          41 :         for(BinHeapElement *e: container)
      45          22 :             delete e;
      46          43 :     }
      47             : 
      48             :     /**
      49             :      * @brief Reserve space in the queue.
      50             :      *
      51             :      * Can make subsequent calls to push(T) faster. See the documentation of
      52             :      * e.g. std::vector::reserve(size_t) for more details on the way this
      53             :      * function works.
      54             :      *
      55             :      * @param sz Capacity of the queue
      56             :      */
      57          14 :     void reserve(size_t sz) {
      58          14 :         container.reserve(sz);
      59          14 :     }
      60             : 
      61             :     /**
      62             :      * @brief Get top element
      63             :      *
      64             :      * Complexity is \f$O(1)\f$.
      65             :      */
      66       14716 :     virtual T top() {
      67       14716 :         return container[1]->getValue();
      68             :     }
      69             : 
      70       14839 :     virtual size_t size() {
      71       14839 :         return container.size() - 1;
      72             :     }
      73             : 
      74             :     /**
      75             :      * @brief Push new element into queue
      76             :      *
      77             :      * Complexity is \f$O(\log N)\f$.
      78             :      */
      79       14790 :     virtual typename PriorityQueue<T>::Element &push(T t) {
      80       14790 :         BinHeapElement *it = new BinHeapElement(*this, container.size(), t);
      81       14790 :         container.push_back(it);
      82             : 
      83       14790 :         heapifyDown(container.size() - 1);
      84             : 
      85       14790 :         return *it;
      86             :     }
      87             : 
      88             :     /**
      89             :      * @brief Pop smallest element of the queue
      90             :      *
      91             :      * Complexity is \f$O(\log N)\f$.
      92             :      */
      93       14788 :     virtual T pop() {
      94       14788 :         T ret = container.at(1)->getValue();
      95             : 
      96       14787 :         BinHeapElement::swap(container[1], container[container.size() - 1]);
      97       14787 :         delete container[container.size() - 1];
      98       14787 :         container.pop_back();
      99             : 
     100       14787 :         heapifyUp(1);
     101             : 
     102       14787 :         return ret;
     103             :     }
     104             : 
     105             :    private:
     106       14787 :     void heapifyUp(size_t i) {
     107       75239 :         while(true) {
     108       90026 :             size_t l = i << 1;
     109       90026 :             size_t r = l | 1;
     110             : 
     111       90026 :             size_t smallest = i;
     112             : 
     113      100586 :             if(l < container.size() && container[l]->getValue() < container[smallest]->getValue()) {
     114             :                 smallest = l;
     115             :             }
     116             : 
     117      133162 :             if(r < container.size() && container[r]->getValue() < container[smallest]->getValue()) {
     118       34584 :                 smallest = r;
     119             :             }
     120             : 
     121       90026 :             if(smallest == i) break;
     122             : 
     123       75239 :             BinHeapElement::swap(container[i], container[smallest]);
     124       75239 :             i = smallest;
     125             :         }
     126       14787 :     }
     127             : 
     128       14942 :     void heapifyDown(size_t i) {
     129       47496 :         while(i > 1) {
     130       43010 :             size_t p = i >> 1;
     131       53461 :             if(container[i]->getValue() < container[p]->getValue()) {
     132       32554 :                 BinHeapElement::swap(container[i], container[p]);
     133             :             } else
     134             :                 break;
     135       32554 :             i = p;
     136             :         }
     137       14942 :     }
     138             : };
     139             : }  // namespace Alg