transforming max-heap into min-heap with heapfy

Question

I'm trying to heapfy a max-heap i've got into a min-heap. For some reason i'm not getting the result i expect.

i've built my max-heap and the array contents of it are showing as expected:

60 50 30 20 40 10

When trying heapfy the above array and transform it into a min-heap, the desired result is:

10 20 30 60 50 40

However, the result i'm getting is:

10 20 60 50 40 30

here are my functions:

struct _heap
{
    int max; //array max
    int pos; //current position
    int* priority; //array gets initialized after.
};

typedef struct _heap heap_t;

void heapify_min(heap_t* h, int father)
{
    int smallest = father;
    int left = 2 * father + 1;
    int right = 2 * father + 2;

    if (left < h->pos && h->priority[left] < h->priority[smallest) {
        smallest = left;
    }
    if (dir < h->pos && h->priority[right] < h->priority[smallest])
        smallest = right;
    if (smallest != father) {
        swap(father,smallest,h->priority);
        heapify_min(h,left);
    }
}

void swap(int a, int b, int *v)
{
    int f = v[a];
    v[a] = v[b];
    v[b] = f;
}


void build_heap(heap_t* h)
{
    int n = h->pos;
    int i2 = (n/2) -1;
    int i;
    for (i = i2;i>=0;i--) {
        heapify_min(h,i);
    }
}

Any insights would be really helpful.

Samuel B. · Answer 1 · 2021-08-18T19:42:46.920

Check your code against my (below is working code for min_heap). There are 3 problems :

In heapify_min function when you calling function recursively you should use variable smallest not left.
operators of comparing values in MIN HEAP should be > (greater) instead of < (smaller)
Function build_heap is correct but that should be just very first rearrange of array. And after that first rearrange of array (first creation of max heap) you should swap first and last element in array. After that initial swap you continue with heapify function but every further creation of max heap, swapping values in sub-trees (during recursive calling) and swaping first element with last element is done in cycle until there is only one node left.

Here is code :

void heapify(int arr[], int n, int i)
{
    int smallest = i;
    int l = 2 * i + 1;
    int r = 2 * i + 2;

    // If left child is larger than root
    if (l < n && arr[l] > arr[smallest])
        smallest = l;

    // If right child is larger than largest so far
    if (r < n && arr[r] > arr[smallest])
       smallest = r;

    // If largest is not root
    if (smallest != i) {

        //swap
        int backUp = arr[i];
        arr[i] = arr[smallest];
        arr[smallest] = backUp;

        // Recursively call on heapify function
        heapify(arr, n, smallest);
     }
  }

  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--) {

      // Swap root node with last node in array (WARNING: last node don't have to be 
     necessarily smallest one)
     int backUp = arr[0];
     arr[0] = arr[i];
     arr[i] = backUp;

     // call max heapify on the reduced heap
     heapify(arr, i, 0);
   }
}

    /* A utility function to print array of size n */
   void printArray(int arr[], int n)
   {
         for (int i = 0; i < n; ++i)
         printf("%d ", arr[i]);

         printf("\n");
   }

transforming max-heap into min-heap with heapfy

1 Answers1