SHARE
TWEET

Untitled

a guest Dec 12th, 2019 60 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #pragma once
  2. #include <iostream>
  3. #include <time.h>
  4. #include <exception>
  5. #include <random>
  6. #include <string>
  7. template <typename T>
  8. struct node {
  9.     node() {};
  10.     node(T value) : data(value) {}
  11.     T data;
  12. };
  13. template <typename T>
  14. struct kopiec {
  15.     long int size = 0;
  16.     long int capacity = 1;
  17.     node<T>* table = new node<T>[capacity];
  18.     kopiec() {
  19.  
  20.     }
  21.     kopiec(T* tablica, int rozmiar) {
  22.        
  23.         for (int i = 0; i <= rozmiar; i++) {
  24.             node<T> zmienna = tablica[i];
  25.             //nowa[i] = tablica[i];
  26.         }
  27.         size = rozmiar;
  28.         table = tablica;
  29.        
  30.         /*int c = 0;
  31.         std::cout << "Aby posortowac wg top-down podaj 1" << std::endl;
  32.         std::cout << "Aby posortowac wg bottom-up podaj 2" << std::endl;
  33.         std::cin >> c;
  34.         while ((c != 1) && (c != 2)) {
  35.             std::cout << "Podaj 1 lub 2!";
  36.             std::cin >> c;
  37.         }
  38.         if (c == 1) {
  39.             top_Down();
  40.         }
  41.         else if (c == 2) {
  42.             buttom_Up();
  43.         }*/
  44.     }
  45.     ~kopiec() {
  46.         delete[] table;
  47.     }
  48.     int leftChild(int indeks) {
  49.         int left = 2 * indeks;
  50.         if (left <= size && left >= 0) {
  51.             return left;
  52.         }
  53.         else {
  54.             return -1;
  55.         }
  56.     }
  57.     int rightChild(int indeks) {
  58.         int right = 2 * indeks + 1;
  59.         if (right <= size && right >= 0) {
  60.             return right;
  61.         }
  62.         else {
  63.             return -1;
  64.         }
  65.     }
  66.     int parent(int indeks) {
  67.         if (indeks > 0) {
  68.             int rodzic = (indeks - 1) / 2;
  69.             if (rodzic <= size && rodzic >= 0) {
  70.                 return rodzic;
  71.             }
  72.             else {
  73.                 return -1;
  74.             }
  75.         }
  76.         else {
  77.             return -1;
  78.         }
  79.     }
  80.     T getAndDeleteMax() {
  81.         T chwilowy = table[0].data;
  82.         size--;
  83.         table[0] = table[size];
  84.         //przesunięcie tablicy o 1 w lewo
  85.         /*for (int i = 0; i < size; i++) {
  86.             table[i].data = table[i + 1].data;
  87.         }
  88.  
  89.         if (table[0].data < table[1].data) {
  90.             T chwilowyII = table[0].data;
  91.             table[0].data = table[1].data;
  92.             table[1] = chwilowyII;
  93.         }
  94.         if (table[0].data < table[2].data) {
  95.             T chwilowyII = table[0].data;
  96.             table[0].data = table[2].data;
  97.             table[2] = chwilowyII;
  98.         }*/
  99.         przekopcowanieRekWDol(0);
  100.  
  101.         return chwilowy;
  102.     }
  103.     void addNewNode(node<T> newData) {
  104.         if (size < capacity) {
  105.             table[size] = node<T>{ newData };
  106.             size++;
  107.         }
  108.         else {
  109.             capacity = capacity * 2;
  110.             node<T>* biggerTable = new node<T>[capacity];
  111.             for (int i = 0; i < size; i++) {
  112.                 biggerTable[i] = table[i];
  113.             }
  114.             delete[] table;
  115.             table = biggerTable;
  116.             table[size] = node<T>{ newData };
  117.             size++;
  118.         }
  119.         if (size > 1) {
  120.             przekopcowanieRekWGore(size - 1);
  121.         }
  122.     }
  123.     void deleteAll() {
  124.         delete[] table;
  125.     }
  126.     void showAll() {
  127.         for (int i = 0; i < size; i++) {
  128.             std::cout << table[i];
  129.         }
  130.     }
  131.     void przekopcowanieRekWGore(int indeks) {
  132.         auto rodzic = parent(indeks);
  133.         if (rodzic >= 0) {
  134.             T chwilowy = table[rodzic].data;
  135.             if (indeks > 0 && chwilowy < table[indeks].data)
  136.             {
  137.                 table[rodzic].data = table[indeks].data;
  138.                 table[indeks].data = chwilowy;
  139.                 przekopcowanieRekWGore(rodzic);
  140.             }
  141.         }
  142.         else {
  143.             //std::cout << "przekopcowaniewgore nie tak" << std::endl;
  144.         }
  145.     }
  146.     void przekopcowanieRekWDol(int indeks) {
  147.         int largest = indeks;
  148.         int left = leftChild(indeks);
  149.         int right = rightChild(indeks);
  150.  
  151.         if (left > 0 && table[left].data > table[largest].data) {
  152.             largest = left;
  153.         }
  154.         if (right > 0 && table[right].data > table[largest].data) {
  155.             largest = right;
  156.         }
  157.         if (largest != indeks) {
  158.             node<T> chwilowy;
  159.             chwilowy.data = table[indeks].data;
  160.             table[indeks].data = table[largest].data;
  161.             table[largest] = chwilowy;
  162.             //std::cout << indeks << std::endl;
  163.             przekopcowanieRekWDol(largest);
  164.         }
  165.     }
  166.     void sort() {
  167.         for (int i = 0; i <= size; i++) {
  168.             T chwilowy = table[0].data;
  169.             table[0] = table[size];
  170.             przekopcowanieRekWDol(0);
  171.             table[size] = chwilowy;
  172.         }
  173.     }
  174.     void top_Down() {
  175.         //od indeks 1 do ostatniego
  176.         for (int i = 1; i <= size; i++)
  177.         {
  178.             //rodzic elementu < elementu
  179.             while (table[parent(i)].data < table[i].data)
  180.             {
  181.                 przekopcowanieRekWGore(i);
  182.             }
  183.         }
  184.     }
  185.     void buttom_Up() {
  186.         //od ostatniego nie liścia
  187.         for (int i = size; i <= 0; i--)
  188.         {
  189.             //potomek elementu > elementu
  190.             while (table[leftChild(i)].data < table[i].data || table[rightChild(i)].data < table[i].data)
  191.             {
  192.                 przekopcowanieRekWDol(i);
  193.             }
  194.         }
  195.     }
  196. };
  197.  
  198. template <typename T>
  199. std::ostream& operator<<(std::ostream& out, const node<T>& val) {
  200.     out << val.data << std::endl;
  201.     return out;
  202. }
  203. int main() {
  204.     int table[10];
  205.     for (int i = 0; i < 10; i++) {
  206.         table[i] = 10-i;
  207.         std::cout << table[i] << " ";
  208.     }
  209.     std::cout << std::endl;
  210.     kopiec <int> example(table, 10);
  211.     //BucketSort(table, 10);
  212.     for (int i = 0; i < 10; i++) {
  213.         std::cout << table[i] << " ";
  214.     }
  215.     getchar();
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top