Advertisement
Guest User

Untitled

a guest
Aug 18th, 2017
72
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.25 KB | None | 0 0
  1. #ifndef SMART_HEAP_H
  2. #define SMART_HEAP_H
  3.  
  4. #include "SmartDataTable.h"
  5.  
  6. template <typename typ>
  7. class SmartHeap : public SmartDataTable<typ> {
  8.  
  9. public:
  10. // dodanie "pustego" elementu: w kopcu nie jest stosowany indeks 0
  11.     SmartHeap<typ>() { typ a = typ(); (*this) += a; }
  12.  
  13. // interfejs klasy:
  14.  
  15. // przywrocenie ukopcowania po umiesczeniu nowego elementu w korzeniu
  16.     void fixRoot(){ fixDown(1L); }
  17. // przywrocenie ukopcowania po umiesczeniu nowego elementu w ostatnim lisciu
  18.     void fixLast(){ fixUp(SmartDataTable<typ>::getDataSize()); }
  19. // ukopcowanie calej tablicy
  20.     void fixHeap(){ for(long k = SmartDataTable<typ>::getDataSize()>>1; k >= 1; k--) fixDown(k); }
  21.    
  22. private:
  23. // lokalne procedury kopcujace:
  24.     void fixUp(long k){ // przenoszenie elementu w gore kopca (w strone korzenia)
  25.         while(k > 1){          
  26.             if(!((*this)[k>>1] < (*this)[k])) break;
  27.             SmartDataTable<typ>::swap(k, k>>1);
  28.             k = k>>1;
  29.         }
  30.     }
  31.  
  32.     void fixDown(long k){ // przenoszenie elementu w dol kopca (w strone lisci)
  33.         while((k<<1) <= SmartDataTable<typ>::getDataSize()){
  34.             long j = k<<1;
  35.             if(j < SmartDataTable<typ>::getDataSize() && ((*this)[j] < (*this)[j+1])) j++;
  36.             if(!((*this)[k] < (*this)[j])) break;
  37.             SmartDataTable<typ>::swap(k, j);
  38.             k = j;
  39.         }
  40.     }
  41. };
  42.  
  43. #endif
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement