Trouble creating a descending heap sort in 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;
}

I got ascending order to heap sort to function by creating a max heap. I read that to create a descending order heap sort I need to create a min heap which I did as shown by changing heap[newNode] < heap[parent] to heap[newNode] > heap[parent] as shown in the code. However, it is still out order. Therefore, I wanted to do what are the other steps? Do I need to alter reheapDown somehow as well?

Answer 1

Here is heap sort using min heap implementation. Have a look, if it helps!
#include "stdafx.h"

#define LEFT(i)         (2 * (i))
#define RIGHT(i)        (((2 * (i)) + 1))
#define PARENT(i)       ((i) / 2))

void print_heap(int input[], int n)
{
    int i;
    printf("Printing heap: \n");
    for (i = 0; i < n; i++)
        printf("%d ", input[i]);
    printf("\n");
}

void swap_nodes(int *a, int *b)
{
    int tmp;
    tmp = *a;
    *a = *b;
    *b = tmp;
}



void min_heapify(int input[], int i, int n)
{
    int least;
    int l = LEFT(i + 1) - 1; // Get 0 based array index
    int r = RIGHT(i + 1) - 1; // Get 0 based array index

    if (l < n && input[l] < input[i]) {
        least = l;
    } else {
        least = i;
    }

    if (r < n && input[r] < input[least]) {
        least = r;
    }

    if (least != i) {
        swap_nodes(&input[i], &input[least]);
        min_heapify(input, least, n);
    }
}


void heapify(int input[], int n)
{
    for (int i = n/2; i >= 0; i--)
        min_heapify(input, i, n); 
}

void heap_sort(int input[], int n)
{
    heapify(input, n);

    for (int i = n - 1; i >= 1; i--) {
        swap_nodes(&input[0], &input[i]);
        n = n - 1;
        min_heapify(input, 0, n);
    }
}

int _tmain(int argc, _TCHAR* argv[])
{
    int input[] = {5, 3, 17, 10, 84, 19, 6, 22, 9, 1};
    int n = sizeof(input) / sizeof(input[0]);

    print_heap(input, n);
    heap_sort(input, n);
    print_heap(input, n);

    return 0;
}

Answer 2

First of all you need to change every comparison operators accordingly, just take them all and think of the problem.

Secondly you only have to reheapUp to (last/2) to create the heap, because the key at (last/2+1) doesn't have any childs.

And I made some heap-sort in C before and I had way less lines of code, and only had one "heapify" function. You might want to look at your code and try to simplify things.

EDIT : if you want some inspiration here is what I did

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

Answer 3

You need to change all value comparisons you make like heap[root] < heap[largeChildIndex] you didn't mention you changed.