How do I modify this HeapSort method in order to make it sort Arrays containing Int numbers into sorted descending Arrays.
Currently it converts Arrays into sorted Ascending Arrays.
static void Hepify(int[] arr, int index, int heapSize)
{
int l = 2 * index + 1;
int r = 2 * index + 2;
int largest;
if (l < heapSize && arr[l] > arr[index])
largest = l;
else
largest = index;
if (r < heapSize && arr[r] > arr[largest])
largest = r;
if (largest != index)
{
int tmp = arr[largest];
arr[largest] = arr[index];
arr[index] = tmp;
Hepify(arr, largest, heapSize);
}
}
static void BuildHeap(int[] arr)
{
for (int i = arr.Length / 2; i >= 0; i--)
Hepify(arr, i, arr.Length);
}
static void HeapSortAscending(int[] arr)
{
BuildHeap(arr);
int heap_size = arr.Length;
for (int i = arr.Length - 1; i > 0; i--)
{
int tmpa = arr[i];
arr[i] = arr[0];
arr[0] = tmpa;
heap_size--;
Hepify(arr, 0, heap_size);
}
}
EDIT
Got something working with the following code, still it doesn't sort it quite correctly:
static void max_heapify(int[] a, int i, int n)
{
int j, temp;
temp = a[i];
j = 2 * i;
while (j <= n)
{
if (j < n && a[j + 1] > a[j])
j = j + 1;
if (temp > a[j])
break;
else if (temp <= a[j])
{
a[j / 2] = a[j];
j = 2 * j;
}
}
a[j / 2] = temp;
return;
}
static void build_maxheap(int[] a, int n)
{
int i;
for (i = n / 2; i >= 1; i--)
{
max_heapify(a, i, n);
}
}
Thank you in advance.