Advertisement
Guest User

Untitled

a guest
Nov 16th, 2018
84
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.90 KB | None | 0 0
  1. #include <iostream>
  2. #include <iomanip>
  3. using namespace std;
  4.  
  5.  
  6. int GetParent (int index) {
  7. return (index - 1) / 2;
  8. }
  9.  
  10. int Left (int index) {
  11. return 2 * index + 1;
  12. }
  13.  
  14. int Right (int index) {
  15. return 2 * index + 2;
  16. }
  17.  
  18. template <class T>
  19. T Get_max (T* heap) {
  20. return heap[0];
  21. }
  22.  
  23. template <class T>
  24. void SiftUp (T* heap, int heap_size, int index) {
  25. if (index <= 0) {
  26. return;
  27. }
  28. else if (heap[index] > heap[GetParent(index)]) {
  29. swap(heap[index], heap[GetParent(index)]);
  30. SiftUp(heap, heap_size, GetParent(index));
  31. }
  32. }
  33.  
  34. template <class T>
  35. void SiftDown (T* heap, int heap_size, int index) {
  36. int min_index = index;
  37.  
  38. if (2 * index + 1 < heap_size && heap[min_index] < heap[Left(index)]) {
  39. min_index = Left(index);
  40. }
  41.  
  42. if (2 * index + 2 < heap_size && heap[min_index] < heap[Right(index)]) {
  43. min_index = Right(index);
  44. }
  45. swap(heap[index], heap[min_index]);
  46. if (min_index != index) {
  47. SiftDown(heap, heap_size, min_index);
  48. }
  49. }
  50.  
  51. template <class T>
  52. void Insert (T* heap, int& heap_size, T value, T start_index) {
  53. ++heap_size;
  54. int begin = 0;
  55. for (int i = start_index; i < heap_size; ++i) {
  56. if (value < heap[i]) {
  57. begin = i;
  58. break;
  59. }
  60. if (i == heap_size - 1) {
  61. begin = heap_size - 1;
  62. }
  63. }
  64. for (int i = heap_size - 2; i > begin - 1; --i) {
  65. heap[i + 1] = heap[i];
  66. }
  67. heap[begin] = value;
  68. }
  69.  
  70. template <class T>
  71. void ExtractMin (T* heap, int& heap_size) {
  72. swap(heap[0], heap[heap_size - 1]);
  73. --heap_size;
  74. SiftDown(heap, heap_size, 0);
  75. }
  76.  
  77. template <typename T>
  78. void BuildHeap (T* heap, int heap_size) {
  79. for (int i = heap_size / 2 - 1; i >= 0; --i) {
  80. SiftDown(heap, heap_size, i);
  81. }
  82. }
  83.  
  84. template <typename T>
  85. void HeapSort (T* heap, T heap_size) {
  86. BuildHeap(heap, heap_size);
  87. while (heap_size > 0) {
  88. ExtractMin(heap, heap_size);
  89. }
  90. }
  91.  
  92. template <typename T>
  93. void RemoveHeap (T* heap, T& heap_size) {
  94. for (int i = 0; i < heap_size - 2; ++i) {
  95. heap[i] = heap[i + 2];
  96. }
  97. heap_size -= 2;
  98. }
  99.  
  100. int main() {
  101. int heap_size;
  102. cin >> heap_size;
  103. int* heap = new int[2 * heap_size + 1];
  104. double total_sum = 0;
  105.  
  106. for (int i = 0; i < heap_size; ++i) {
  107. cin >> heap[i];
  108. }
  109. int start_index = 0;
  110. int size_of_first_heap = heap_size;
  111. HeapSort(heap, heap_size);
  112. for (int i = 0; i < size_of_first_heap - 1; ++i) {
  113. int current_sum = heap[2 * i] + heap[2 * i + 1];
  114. heap[2 * i] = -1;
  115. heap[2 * i + 1] = -1;
  116. total_sum += current_sum;
  117. start_index += 1;
  118. Insert(heap, heap_size, current_sum, start_index);
  119. }
  120. cout << fixed;
  121. cout << setprecision(2) << total_sum * 0.05;
  122.  
  123. delete [] heap;
  124. return 0;
  125. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement