c - 在 C 中创建降序堆排序时遇到问题

Question

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不知何故也是如此？

Answer 1

您需要更改所有进行的值比较，例如 heap[root] < heap[largeChildIndex]你没有提到你改变了。