преобразование max-heap в min-heap с помощью heapfy

Question

Я пытаюсь заполнить максимальную кучу, я попал в минимальную кучу. По какой-то причине я не получаю ожидаемого результата.

Я построил свою максимальную кучу, и содержимое ее массива отображается, как ожидалось:

60 50 30 20 40 10

При попытке скопировать указанный выше массив и преобразовать его в минимальную кучу желаемый результат:

10 20 30 60 50 40

Однако результат, который я получаю:

10 20 60 50 40 30

вот мои функции:

      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);
    }
}

Любые идеи были бы действительно полезны.

Answer 1

Привет, я думаю, что ваша максимальная куча не работает должным образом, потому что на выходе: 60 50 30 20 40 10 Я вижу, что 40 - это второе число с правой стороны в массиве.

Сравните свой код с моим (ниже рабочий код для min_heap). Есть 3 проблемы:

1. В функции heapify_min, когда вы вызываете функцию рекурсивно, вы должны использовать наименьшую не оставшуюся переменную .

2. операторы сравнения значений в MIN HEAP должны быть> (больше) вместо <(меньше)

3. Функция build_heap верна, но это должна быть самая первая перестановка массива. И после этой первой перестановки массива (первого создания максимальной кучи) вы должны поменять местами первый и последний элемент в массиве. После этого начального свопа вы продолжаете использовать функцию heapify, но каждое последующее создание максимальной кучи, замена значений в поддеревьях (во время рекурсивного вызова) и замена первого элемента последним выполняется в цикле до тех пор, пока не останется только один узел.

Вот код:

      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");
   }