Convert min Heap to max Heap - GeeksforGeeks
Given array representation of min Heap, convert it to max Heap in O(n) time.
The problem might look complex at first look. But our final goal is to only build the max heap. The idea is very simple – we simply build Max Heap without caring about the input. We start from bottom-most and rightmost internal mode of min Heap and heapify all internal modes in bottom up way to build the Max heap.
Read full article from Convert min Heap to max Heap - GeeksforGeeks
Given array representation of min Heap, convert it to max Heap in O(n) time.
The problem might look complex at first look. But our final goal is to only build the max heap. The idea is very simple – we simply build Max Heap without caring about the input. We start from bottom-most and rightmost internal mode of min Heap and heapify all internal modes in bottom up way to build the Max heap.
The complexity of above solution might looks like O(nLogn) but it is O(n). Refer this G-Fact for more details.
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); }}// This function basically builds max heapvoid convertMaxHeap(int arr[], int n){ // Start from bottommost and rightmost // internal mode and heapify all internal // modes in bottom up way for (int i = (n-2)/2; i >= 0; --i) MaxHeapify(arr, i, n);}