Guest User

Untitled

a guest
Dec 12th, 2019
69
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