Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // A C++ program to convert min Heap to max Heap
- #include<bits/stdc++.h>
- using namespace std;
- void MaxHeapify(int arr[], int i, int n)
- {
- int l = 2*i + 1;
- int r = 2*i + 2;
- int largest = i;
- if (l < n && arr[l] > arr[i])
- largest = l;
- if (r < n && arr[r] > arr[largest])
- largest = r;
- if (largest != i)
- {
- swap(arr[i], arr[largest]);
- MaxHeapify(arr, largest, n);
- }
- }
- void convertMaxHeap(int arr[], int n)
- {
- for (int i = (n-2)/2; i >= 0; --i)
- MaxHeapify(arr, i, n);
- }
- void printArray(int* arr, int size)
- {
- for (int i = 0; i < size; ++i)
- printf("%d ", arr[i]);
- }
- void heapify(int arr[], int n, int i)
- {
- int largest = i; // Initialize largest as root
- int l = 2*i + 1; // left = 2*i + 1
- int r = 2*i + 2; // right = 2*i + 2
- // If left child is larger than root
- if (l < n && arr[l] > arr[largest])
- largest = l;
- // If right child is larger than largest so far
- if (r < n && arr[r] > arr[largest])
- largest = r;
- // If largest is not root
- if (largest != i)
- {
- swap(arr[i], arr[largest]);
- // Recursively heapify the affected sub-tree
- heapify(arr, n, largest);
- }
- }
- void heapSort(int arr[], int n)
- {
- // Build heap (rearrange array)
- for (int i = n / 2 - 1; i >= 0; i--)
- heapify(arr, n, i);
- // One by one extract an element from heap
- for (int i=n-1; i>=0; i--)
- {
- // Move current root to end
- swap(arr[0], arr[i]);
- // call max heapify on the reduced heap
- heapify(arr, i, 0);
- }
- }
- bool isHeap(int level[], int n)
- {
- // First non leaf node is at index (n/2-1).
- // Check whether each parent is greater than child
- for (int i=(n/2-1) ; i>=0 ; i--)
- {
- // Left child will be at index 2*i+1
- // Right child will be at index 2*i+2
- if (level[i] > level[2 * i + 1])
- return false;
- if (2*i + 2 < n)
- {
- // If parent is greater than right child
- if (level[i] > level[2 * i + 2])
- return false;
- }
- }
- return true;
- }
- int main()
- {
- 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,
- 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,
- 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};
- int n = sizeof(arr)/sizeof(arr[0]);
- convertMaxHeap(arr, n);
- // printf("Max Heap array : ");
- // printArray(arr, n);
- cout<<"Primele 5 elemente sunt: ";
- printArray(arr, 5);
- cout<<"Elementele de pe al 3-lea nivel sunt: ";
- for(int i=7;i<=14;i++)cout << arr[i] << " ";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement