Проблема с созданием сортировки кучи по убыванию в C

void heapSort(int list[], int last) 
{
     // Local Declarations
     int sorted;
     int holdData;
     int walker;

     // Statements
     for (walker = 1; walker <= last; walker++)
          reheapUp (list, walker);

     // Min Heap created. Now to sort!
     sorted = last;
     while (sorted > 0)
     {
           holdData = list[0];
           list[0] = list[sorted];
           list[sorted] = holdData;
           sorted--;
           reheapDown (list, 0, sorted, moves, comparisons);
     }

     return;
}

void reheapUp (int heap[], int newNode)
{
     // Local Declarations
     int parent;
     int hold;

     // Create a min heap
     // Statements
     if (newNode)
     {
          parent = (newNode - 1) / 2;
          if (heap[newNode] > heap[parent]) // Only change made from ascending order
          {
               hold = heap[parent];
               heap[parent] = heap[newNode];
               heap[newNode] = hold;
               reheapUp (heap, parent);
          }
     }

     return;
}

void reheapDown (int heap[], int root, int last)
{
     // Local Declarations
     int hold;
     int leftKey;
     int rightKey;
     int largeChildKey;
     int largeChildIndex;

     // Statements
     if ((root * 2 + 1) <= last)
     {    
          // There is atleast one child
          leftKey = heap[root * 2 + 1];
          if ((root * 2 + 2) <= last) {
               rightKey = heap[root * 2 + 2];
          }
          else
               rightKey = -1;

          // Determine which child is larger
          if (leftKey > rightKey)
          {
               largeChildKey = leftKey;
               largeChildIndex = root * 2 + 1;
          }
          else
          {
               largeChildKey = rightKey;
               largeChildIndex = root * 2 + 2;
          }
          // Test if root > large subtree
          if (heap[root] < heap[largeChildIndex])
          {    
               // parent < child
               hold = heap[root];
               heap[root] = heap[largeChildIndex];
               heap[largeChildIndex] = hold;
               reheapDown(heap, largeChildIndex, last);
          }
     }

     return;
}

Я получил порядок сортировки кучи по возрастанию, создав максимальную кучу. Я прочитал, что для создания сортировки кучи в порядке убывания мне нужно создать минимальную кучу, которую я сделал, как показано, изменив heap[newNode] < heap[parent] на heap[newNode] > heap[parent], как показано в коде. Тем не менее, это все еще не в порядке. Поэтому я хотел сделать, какие еще шаги? Нужно ли как-то переделывать и reheapDown?


c heapsort
person skalidindi    schedule 30.05.2011    source источник
comment
Вам нужно поменять местами все ключевые сравнения, а не только одно. У вас есть как минимум leftKey > rightKey и heap[root] < heap[largeChildIndex], которые нужно проверить.   -  person n. 1.8e9-where's-my-share m.    schedule 31.05.2011
comment
И не забудьте принять ответ.   -  person Sword22    schedule 02.06.2011

Ответы (2)


arrow_upward
1
arrow_downward

Вам нужно изменить все сравнения значений, которые вы делаете, например heap[root] < heap[largeChildIndex], вы не упомянули, что изменились.

person Dani    schedule 30.05.2011

arrow_upward
0
arrow_downward

Прежде всего, вам нужно соответствующим образом изменить все операторы сравнения, просто возьмите их все и подумайте о проблеме.

Во-вторых, вам нужно только reheapUp до (last/2), чтобы создать кучу, потому что ключ в (last/2+1) не имеет дочерних элементов.

И я сделал некоторую сортировку кучей в C раньше, и у меня было намного меньше строк кода, и у меня была только одна функция «heapify». Возможно, вы захотите взглянуть на свой код и попытаться упростить его.

РЕДАКТИРОВАТЬ: если вам нужно вдохновение, вот что я сделал

void fixHeap(int position,int length) 
{
    int child = (2*position)+1; 
    int temp;                

    while (child<=length)
    {
        if (child<length && vector[child]<vector[child+1])
        {
            child++;
        }

        if (vector[position]<vector[child])
        {
            temp = vector[position];   
            vector[position] = vector[child];
            vector[child] = temp;
            position = child;   
            child = (2*position)+1;
        }
        else
        {
            return;
        }
    }
}

void heapSort(int vector[],int N) 
{
    int counter;
    int temp; 

    for (counter=(N-1)/2; counter>=0; counter--) 
    {
        fixHeap(counter,N-1); 
    }
    for (counter=N-1; counter>0; counter--) 
    {
        temp = vector[counter]; 
        vector[counter] = vector[0];
        vector[0] = temp;
        fixHeap(0,counter-1); 
    }
}
person Sword22    schedule 30.05.2011