Pinkel

Kopiec i kolejka priorytetowa

Jan 11th, 2018
109
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.70 KB | None | 0 0
  1. #include <iostream>
  2. #include <ctime>
  3. #include <stdlib.h>
  4. using namespace std;
  5.  
  6.  
  7.  
  8. const int N = 11;
  9. int kopiec[N] = {15,12,11,10,11,8,5,3,7,2,9}; //przykładowy kopiec
  10.  
  11. void print(int tab[], int n)
  12. {
  13. for(int i = 0; i< n; i++)
  14. cout<< tab[i] << " ";
  15. cout<<endl;
  16. }
  17.  
  18. void zanurzanie(int tab[], int i, int rozmiar)
  19. {
  20. int wiekszy;
  21. int lewy = 2*i + 1;
  22. int prawy = 2*i + 2;
  23. if(lewy < rozmiar && tab[lewy] > tab[i])
  24. wiekszy = lewy;
  25. else
  26. wiekszy = i;
  27. if(prawy < rozmiar && tab[prawy] > tab[wiekszy])
  28. wiekszy = prawy;
  29. if(wiekszy != i)
  30. {
  31. swap(tab[i], tab[wiekszy]);
  32. zanurzanie(tab, wiekszy, rozmiar);
  33. }
  34. }
  35.  
  36. void wynurzanie(int tab[], int i)
  37. {
  38. if(i > 0)
  39. {
  40. int ojciec = (i-1)/2;
  41. if(tab[i] > tab[ojciec])
  42. {
  43. swap(tab[i], tab[ojciec]);
  44. wynurzanie(tab, ojciec);
  45. }
  46. }
  47. }
  48.  
  49. const int K = 5;
  50. int rozmiarKolejki = 0;
  51. int kolejka[K] = {0};
  52.  
  53. void insert(int i)
  54. {
  55. if(rozmiarKolejki < K)
  56. {
  57. kolejka[rozmiarKolejki] = i;
  58. wynurzanie(kolejka, rozmiarKolejki);
  59. rozmiarKolejki++;
  60. }
  61. }
  62.  
  63. int extract()
  64. {
  65. if(rozmiarKolejki<1)
  66. cout<<"Kolejka pusta"<<endl;
  67. else
  68. {
  69. cout<<"[-]: ";
  70. rozmiarKolejki--;
  71. swap(kolejka[0], kolejka[rozmiarKolejki]);
  72. kolejka[rozmiarKolejki]= 0;
  73. zanurzanie(kolejka,0, K);
  74. }
  75. }
  76.  
  77. int wywolaj_kolejke()
  78. {
  79. insert(12);
  80. print(kolejka, K);
  81. insert(15);
  82. print(kolejka, K);
  83. insert(10);
  84. print(kolejka, K);
  85. insert(3);
  86. print(kolejka, K);
  87. extract();
  88. print(kolejka, K);
  89. extract();
  90. print(kolejka, K);
  91. insert(7);
  92. print(kolejka, K);
  93. insert(5);
  94. print(kolejka, K);
  95. insert(9);
  96. print(kolejka, K);
  97. insert(11);
  98. print(kolejka, K);
  99. extract();
  100. print(kolejka, K);
  101. extract();
  102. print(kolejka, K);
  103. extract();
  104. print(kolejka, K);
  105. extract();
  106. print(kolejka, K);
  107. extract();
  108. print(kolejka, K);
  109. extract();
  110. print(kolejka, K);
  111. }
  112.  
  113. const int S = 20;
  114. int sortowanie[S];
  115.  
  116. void wstaw()
  117. {
  118. srand(time(NULL));
  119. for(int i = 0 ; i < S ; i++)
  120. sortowanie[i] = rand()%10;
  121. print(sortowanie, S);
  122. }
  123.  
  124. void sortuj(int rozmiar)
  125. {
  126. wstaw();
  127. //twoerzenie kopca
  128. for(int i = (rozmiar-1)/2; i>=0; i--)
  129. zanurzanie(sortowanie, i, rozmiar);
  130. for(int i = rozmiar-1; i>0; i--)
  131. {
  132. swap(sortowanie[0], sortowanie[i]);
  133. rozmiar--;
  134. zanurzanie(sortowanie, 0, rozmiar);
  135. }
  136. print(sortowanie, S);
  137. }
  138.  
  139.  
  140.  
  141.  
  142. int main(){
  143. sortuj(S);
  144. return 0;
  145. }
Add Comment
Please, Sign In to add comment