Chuyển đổi Heap tối thiểu thành Heap tối đa trong C ++

Trong hướng dẫn này, chúng ta sẽ thảo luận về một chương trình để chuyển đổi min heap thành max heap.

Đối với điều này, chúng tôi sẽ được cung cấp với biểu diễn mảng của đống tối thiểu. Nhiệm vụ của chúng tôi là chuyển đổi heap tối thiểu đó thành heap tối đa với độ phức tạp thời gian O (n).

Ví dụ

#include<bits/stdc++.h>
using namespace std;
//converting a given subtree into a heap
void convert_arrayheap(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]);
      convert_arrayheap(arr, largest, n);
   }
}
//finally building the max heap
void convert_maxheap(int arr[], int n){
   //heapify all the node elements
   for (int i = (n-2)/2; i >= 0; --i)
   convert_arrayheap(arr, i, n);
}
//printing the array
void printArray(int* arr, int size){
   for (int i = 0; i < size; ++i)
   printf("%d ", arr[i]);
}
int main(){
   int arr[] = {3, 5, 9, 6, 8, 20, 10, 12, 18, 9};
   int n = sizeof(arr)/sizeof(arr[0]);
   printf("Min Heap array : ");
   printArray(arr, n);
   convert_maxheap(arr, n);
   printf("\nMax Heap array : ");
   printArray(arr, n);
   return 0;
}

Đầu ra

Min Heap array : 3 5 9 6 8 20 10 12 18 9
Max Heap array : 20 18 10 12 9 9 3 5 6 8