Facebook
From Colorant Goat, 4 Months ago, written in Plain Text.
Embed
Download Paste or View Raw
Hits: 69
  1. #include "Heap.hxx"
  2.  
  3. // Wersja iteracyjna
  4. void Heap::heapifyIter(int i) {
  5.  
  6.      int largest, c1, c2;
  7.      while(i < max) {
  8.           //compareMin++;
  9.           //compareMax++;
  10.  
  11.           largest = i;
  12.           c1 = 2*i;
  13.           c2 = c1 + 1;
  14.  
  15.           //compareMin++;
  16.           //compareMax += 2;
  17.           if(c1 < max && heap[c1] > heap[largest]) largest = c1;
  18.  
  19.           //compareMin++;
  20.           //compareMax += 2;
  21.           if(c2 < max && heap[c2] > heap[largest]) largest = c2;
  22.          
  23.           //compareMin++;
  24.           //compareMax++;
  25.           if(largest == i) return;
  26.           //swap += 3;
  27.           std::swap(heap[i],heap[largest]);
  28.           i = largest;
  29.      }
  30.      //compareMax++;
  31.      //compareMin++;
  32. }
  33.  
  34. // Wersja rekurencyjna
  35. void Heap::heapifyRec(int i) {
  36.      int largest, c1, c2;
  37.      while(i < max) {
  38.           //compareMax++;
  39.           //compareMin++;
  40.  
  41.           largest = i;
  42.           c1 = 2*i;
  43.           c2 = c1 + 1;
  44.  
  45.           //compareMin++;
  46.           //compareMax += 2;
  47.           if(c1 < max && heap[c1] > heap[largest]) largest = c1;
  48.  
  49.           //compareMin++;
  50.           //compareMax += 2;
  51.           if(c2 < max && heap[c2] > heap[largest]) largest = c2;
  52.  
  53.           //compareMin++;
  54.           //compareMax++;
  55.           if(largest == i) return;
  56.  
  57.           //swap += 3;
  58.           std::swap(heap[largest], heap[i]);
  59.           heapifyRec(largest);
  60.      }
  61.  
  62.      //ompareMax++;
  63.      //compareMin++;
  64. }
  65.  
  66. void Heap::build(int *a, int s) {
  67.      heap.clear();
  68.      // Wrzucam cokolwiek na pozycje 0
  69.      heap.push_back(s);
  70.      for(int i = 0; i < s; i++) {
  71.           heap.push_back(a[i]);
  72.      }
  73.      this->max = s+1;
  74.  
  75.      for(int i = s/2; i >= 1; i--) {
  76.           //compareMax++;
  77.           //compareMin++;
  78.           heapifyIter(i);
  79.      }
  80.      //compareMax++;
  81.      //compareMin++;
  82. }
  83. // Wstawia element do kopca
  84. void Heap::push(int x) {
  85.      int i = heap[0]++;   // zwieksza ilo┼Ť─ç elementow w tablicy
  86.      max = heap[0];
  87.      heap[i] = x;
  88.  
  89.      int half = i/2;
  90.      while(i > 1 && heap[i] > heap[half]) {
  91.           std::swap(heap[i],heap[half]);
  92.           i = half;
  93.           half = i/2;
  94.      }
  95. }
  96. // Usuwa element z kopca
  97. int Heap::hop() {
  98.      if(!empty()) {
  99.           int ret = heap[1];
  100.           heap.erase(++heap.begin());
  101.           std::swap(heap[1], heap[heap.size()-1]);
  102.          
  103.          
  104.           for(int i = size()/2; i >= 1; i--) {
  105.                heapifyRec(i);
  106.           }
  107.          
  108.           max--;
  109.           return ret;
  110.      }
  111.      return -1;
  112. }  
  113. // Zwraca referncj─Ö do ostatniego elementu
  114. int& Heap::top() {
  115.      return this->heap[size()-1];
  116. }
  117. // Zwraca liczb─Ö element├│w w kopcu      
  118. int Heap::size() {
  119.      return heap.size()-1;
  120. }
  121. // Sprawdza czy kopiec jest pusty
  122. bool Heap::empty() {
  123.      return heap.size()==1;
  124. }
  125.  
  126. // Sprawdza czy w┼éa┼Ťciwo┼Ť─ç kopca jest zachowana
  127. bool Heap::check() {
  128.      int s = size();
  129.      int half = s/2, ix2;
  130.      for(int i = 1; i <= half; i = ix2) {
  131.           ix2 = 2*i;
  132.           if(ix2 <= s && (heap[i] < heap[ix2])) return false;
  133.           if(ix2+1 <= s && (heap[i] < heap[ix2+1])) return false;
  134.      }
  135.      return true;
  136. }
  137.  
  138. void Heap::sortRec(int * a, int s) {
  139.      build(a, s);
  140.      
  141.      for(int i = size(); i > 1; i--) {
  142.           //compareMin++;
  143.           //compareMax++;
  144.           //swap += 3;
  145.  
  146.           std::swap(heap[1], heap[i]);
  147.           max--;
  148.           heapifyRec(1);
  149.      }
  150.      //compareMin++;
  151.      //compareMax++;
  152. }
  153.  
  154. void Heap::sortIter(int * a, int s) {
  155.      build(a, s);
  156.  
  157.      for(int i = size(); i > 1; i--) {
  158.           //compareMin++;
  159.           //compareMax++;
  160.           //swap += 3;
  161.  
  162.           std::swap(heap[1], heap[i]);
  163.           max--;
  164.           heapifyIter(1);
  165.      }
  166.      //compareMin++;
  167.      //compareMax++;
  168. }
  169.  
  170. void Heap::printHeap() {
  171.      int s = size();
  172.      for(int i = 1; i <= s; i++) {
  173.           printf("%d\n", heap[i]);
  174.      }
  175. }