Advertisement
Guest User

Untitled

a guest
Feb 17th, 2020
107
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.82 KB | None | 0 0
  1. // A C++ program to convert min Heap to max Heap
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4.  
  5. void MaxHeapify(int arr[], int i, int n)
  6. {
  7. int l = 2*i + 1;
  8. int r = 2*i + 2;
  9. int largest = i;
  10. if (l < n && arr[l] > arr[i])
  11. largest = l;
  12. if (r < n && arr[r] > arr[largest])
  13. largest = r;
  14. if (largest != i)
  15. {
  16. swap(arr[i], arr[largest]);
  17. MaxHeapify(arr, largest, n);
  18. }
  19. }
  20.  
  21. void convertMaxHeap(int arr[], int n)
  22. {
  23. for (int i = (n-2)/2; i >= 0; --i)
  24. MaxHeapify(arr, i, n);
  25. }
  26.  
  27. void printArray(int* arr, int size)
  28. {
  29. for (int i = 0; i < size; ++i)
  30. printf("%d ", arr[i]);
  31. }
  32.  
  33. void heapify(int arr[], int n, int i)
  34. {
  35. int largest = i; // Initialize largest as root
  36. int l = 2*i + 1; // left = 2*i + 1
  37. int r = 2*i + 2; // right = 2*i + 2
  38.  
  39. // If left child is larger than root
  40. if (l < n && arr[l] > arr[largest])
  41. largest = l;
  42.  
  43. // If right child is larger than largest so far
  44. if (r < n && arr[r] > arr[largest])
  45. largest = r;
  46.  
  47. // If largest is not root
  48. if (largest != i)
  49. {
  50. swap(arr[i], arr[largest]);
  51.  
  52. // Recursively heapify the affected sub-tree
  53. heapify(arr, n, largest);
  54. }
  55. }
  56.  
  57. void heapSort(int arr[], int n)
  58. {
  59. // Build heap (rearrange array)
  60. for (int i = n / 2 - 1; i >= 0; i--)
  61. heapify(arr, n, i);
  62.  
  63. // One by one extract an element from heap
  64. for (int i=n-1; i>=0; i--)
  65. {
  66. // Move current root to end
  67. swap(arr[0], arr[i]);
  68.  
  69. // call max heapify on the reduced heap
  70. heapify(arr, i, 0);
  71. }
  72. }
  73.  
  74. bool isHeap(int level[], int n)
  75. {
  76. // First non leaf node is at index (n/2-1).
  77. // Check whether each parent is greater than child
  78. for (int i=(n/2-1) ; i>=0 ; i--)
  79. {
  80. // Left child will be at index 2*i+1
  81. // Right child will be at index 2*i+2
  82. if (level[i] > level[2 * i + 1])
  83. return false;
  84.  
  85. if (2*i + 2 < n)
  86. {
  87. // If parent is greater than right child
  88. if (level[i] > level[2 * i + 2])
  89. return false;
  90. }
  91. }
  92. return true;
  93. }
  94.  
  95. int main()
  96. {
  97. int arr[]={17,34,51,68,85,2,19,36,53,70,87,4,21,38,55,72,89,6,23,40,57,74,91,8,25,42,59,76,93,10,27,44,
  98. 61,78,95,12,29,46,63,80,97,14,31,48,65,82,16,33,50,67,84,1,18,35,52,69,86,3,20,37,54,71,88,5,
  99. 22,39,56,73,90,7,24,41,58,75,92,9,26,43,60,77,94,11,28,45,62,79,96,13,30,47,64,81,15,32,49,83};
  100.  
  101. int n = sizeof(arr)/sizeof(arr[0]);
  102. convertMaxHeap(arr, n);
  103.  
  104. // printf("Max Heap array : ");
  105. // printArray(arr, n);
  106.  
  107. cout<<"Primele 5 elemente sunt: ";
  108.  
  109. printArray(arr, 5);
  110.  
  111.  
  112. cout<<"Elementele de pe al 3-lea nivel sunt: ";
  113. for(int i=7;i<=14;i++)cout << arr[i] << " ";
  114.  
  115.  
  116. return 0;
  117. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement