Facebook
From Sayem, 9 Months ago, written in C++.
Embed
Download Paste or View Raw
Hits: 407
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int parent(int i){
  5.     return i/2;
  6. }
  7. int left(int i){
  8.     return 2*i+1
  9. }
  10. int right(int i){
  11.     return 2*i+2
  12. }
  13. void maxheap(int a, int i){
  14.     int l = left(i);
  15.     int r = right(i);
  16.     if (l>a[l]){
  17.         largest=l;
  18.     }
  19.     else () {largest = i};
  20.     if
  21. }
  22.  
  23. void maxheap(int A[], int heapSize, int i) {
  24.     int largest = i;
  25.     int l = 2 * i + 1;
  26.     int r = 2 * i + 2;
  27.  
  28.     if (l < heapSize && A[l] > A[largest]) {
  29.         largest = l;
  30.     }
  31.  
  32.     if (r < heapSize && A[r] > A[largest]) {
  33.         largest = r;
  34.     }
  35.  
  36.     if (largest != i) {
  37.         swap(A[i], A[largest]);
  38.         maxheap(A, heapSize, largest);
  39.     }
  40. }
  41.  
  42.  
  43.  
  44.  
  45.  
  46. int main(){
  47.     int element[] = {23, 17, 14, 6, 13, 10, 1, 5, 7, 12};
  48.     int arraySize = sizeof(element)/sizeof(element[0]);
  49.  
  50.         cout << "Before MAX_HEAPIFY: ";
  51.     for (int i = 0; i < arraySize; i++)
  52.     {
  53.         cout << A[i] << " ";
  54.     }
  55.     cout << endl;
  56.  
  57.     MAX_HEAPIFY(A, arraySize, 0);
  58.  
  59.     cout << "After MAX_HEAPIFY: ";
  60.     for (int i = 0; i < arraySize; i++)
  61.     {
  62.         cout << A[i] << " ";
  63.     }
  64.     cout << endl;
  65.  
  66.     return 0;
  67. }
  68.  
  69.  
  70. ________________________________________________
  71.  
  72. #include <iostream>
  73. using namespace std;
  74.  
  75.  
  76. void MAX_HEAPIFY(int A[], int heapSize, int i)
  77. {
  78.     int largest = i;
  79.     int l = 2 * i + 1;
  80.     int r = 2 * i + 2;
  81.  
  82.     if (l < heapSize && A[l] > A[largest])
  83.     {
  84.         largest = l;
  85.     }
  86.  
  87.     if (r < heapSize && A[r] > A[largest])
  88.     {
  89.         largest = r;
  90.     }
  91.  
  92.     if (largest != i)
  93.     {
  94.         swap(A[i], A[largest]);
  95.         MAX_HEAPIFY(A, heapSize, largest);
  96.     }
  97. }
  98.  
  99. int main()
  100. {
  101.     int A[] = {4, 10, 3, 5, 1};
  102.     int heapSize = sizeof(A)/sizeof(A[0]);
  103.  
  104.  
  105.  
  106.     return 0;
  107. }
  108.  
  109.  
  110. _________________________________________________________
  111.  
  112. #include<bits/stdc++.h>
  113. using namespace std;
  114.  
  115. int parent(int i){
  116.     return i/2;
  117. }
  118.  
  119. int left(int i){
  120.     return 2*i+1;
  121. }
  122.  
  123. int right(int i){
  124.     return 2*i+2;
  125. }
  126.  
  127. void maxheap(int A[], int heapSize, int i) {
  128.     int largest = i;
  129.     int l = left(i);
  130.     int r = right(i);
  131.  
  132.     if (l < heapSize && A[l] > A[largest]) {
  133.         largest = l;
  134.     }
  135.  
  136.     if (r < heapSize && A[r] > A[largest]) {
  137.         largest = r;
  138.     }
  139.  
  140.     if (largest != i) {
  141.         swap(A[i], A[largest]);
  142.         maxheap(A, heapSize, largest);
  143.     }
  144. }
  145.  
  146. void buildMaxHeap(int A[], int heapSize) {
  147.     for (int i = heapSize / 2 - 1; i >= 0; i--) {
  148.         maxheap(A, heapSize, i);
  149.     }
  150. }
  151.  
  152. void heapSort(int A[], int heapSize) {
  153.     buildMaxHeap(A, heapSize);
  154.     for (int i = heapSize - 1; i >= 1; i--) {
  155.         swap(A[0], A[i]);
  156.         maxheap(A, i, 0);
  157.     }
  158. }
  159.  
  160. int main(){
  161.     int element[] = {23, 17, 14, 6, 13, 10, 1, 5, 7, 12};
  162.     int arraySize = sizeof(element)/sizeof(element[0]);
  163.  
  164.     heapSort(element, arraySize);
  165.  
  166.     cout << "Sorted array: ";
  167.     for (int i = 0; i < arraySize; i++) {
  168.         cout << element[i] << " ";
  169.     }
  170.     cout << endl;
  171.  
  172.     return 0;
  173. }
  174.  
  175. ____________________________________________________
  176.  
  177.