EWTD

Heap

Nov 5th, 2018
239
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. template<typename T>
  2. struct Heap {
  3.  
  4.     explicit Heap(size_t size) {
  5.         _Size = size;
  6.         try {
  7.             _Tree = (T *) malloc( _Size * sizeof(T));
  8.         }
  9.         catch(...){
  10.             std::cerr << "NOMEM" ;
  11.             exit(1);
  12.         }
  13.     }
  14.  
  15.     Heap() {
  16.         try {
  17.             _Tree = (T *) malloc( _Size * sizeof(T));
  18.         }
  19.         catch(...){
  20.             std::cerr << "NOMEM" ;
  21.             exit(1);
  22.         }
  23.     }
  24.  
  25.     inline bool is_empty() {
  26.         return _elemSize == 0;
  27.     }
  28.  
  29.     T top() {
  30.         try{
  31.             if (is_empty()){
  32.                 throw;
  33.             }
  34.             return _Tree[0];
  35.         }
  36.         catch (...){
  37.             std::cerr << "Err: Heap is empty" << '\n';
  38.         }
  39.  
  40.     }
  41.  
  42.     void push(T value) {
  43.         if (_elemSize == _Size) {
  44.             _resize();
  45.         }
  46.         _Tree[_elemSize++] = value;
  47.         siftUp(_elemSize - 1);
  48.     }
  49.  
  50.     void pop() {
  51.         if (!is_empty()) {
  52.             _Tree[0] = _Tree[--_elemSize];
  53.             siftDown(0);
  54.         } else {
  55.             std::cerr << "Err: Heap is empty" << '\n';
  56.         }
  57.  
  58.     }
  59.  
  60.     void clear() {
  61.             _elemSize = 0;
  62.     }
  63.  
  64.  
  65.     ~Heap() {
  66.         free(_Tree);
  67.     }
  68.  
  69. private:
  70.     T *_Tree;
  71.     size_t _elemSize = 0;
  72.     size_t _Size = 4;
  73.  
  74.     void siftUp(size_t index) {
  75.         while (index > 0 && _Tree[index] > _Tree[(index - 1) / 2]) {
  76.             std::swap(_Tree[index], _Tree[(index - 1) / 2]);
  77.             index = (index - 1) / 2;
  78.         }
  79.     }
  80.  
  81.     void siftDown(size_t index) {
  82.         while (2 * index + 1 < _elemSize) {
  83.             size_t lch = 2 * index + 1;
  84.             size_t rch = 2 * index + 2;
  85.             size_t maxCh = lch;
  86.             if (rch < _elemSize && _Tree[rch] > _Tree[maxCh]) {
  87.                 maxCh = rch;
  88.             }
  89.             if (_Tree[index] >= _Tree[maxCh])
  90.                 return;
  91.             std::swap(_Tree[index], _Tree[maxCh]);
  92.             index = maxCh;
  93.         }
  94.     }
  95.  
  96.     void _resize() {
  97.         try {
  98.             _Tree = (T *) realloc(_Tree, _Size * 2 * sizeof(T));
  99.             _Size *= 2;
  100.         }
  101.         catch(...){
  102.             std::cerr << "NOMEM" ;
  103.             exit(1);
  104.         }
  105.     }
  106. };
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×