Hello there
I am implementing heap sort by maintaining min heap property. It is working fine but the order is descending, I want ascending order.
One way is to invert the output array and get the desired output but this is not what I want. Like in min heap root is the smallest element, now I am replacing root element of the array with the last and call minheap(A, 1, i-1); I want to keep the root element at its sorted place and calling the minheap something like this minheap(A,2,n); means calling minheap for the rest of array, but this results in two heaps because root is removed. I am stuck at this place.
Please help me, either tell me the algorithm or change my code.
Thanks
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace MinHeapSort
{
class Program
{
static void Main(string[] args){
int[] array = {0,4,1,3,2,16,9,10,14,8,7};
heapSort(array, 10);
}
static void heapSort(int[] A, int n)
{
buildMinHeap(A, n);
for (int i = n; i >= 2; i--)
{
int tmp = A[i];
A[i] = A[1];
A[1] = tmp;
min_heapify(A, 1, i - 1);
}
}
static void buildMinHeap(int[] A, int n){
for (int i =(int) Math.Floor((double)n / 2.0); i >= 1; i--)
min_heapify(A, i, n);
}
static void min_heapify(int[] A, int i, int rightIndex){
int l = leftChild(i);
int r = rightChild(i);
int largest;
if (l <= rightIndex && A[l] < A[i])
largest = l;
else
largest = i;
if (r <= rightIndex && A[r] < A[largest])
largest = r;
if (largest != i)
{
int tmp = A[i];
A[i] = A[largest];
A[largest] = tmp;
min_heapify(A, largest, rightIndex);
}
}
static int parent(int i){
return (int) Math.Floor( (double)i / 2.0);
}
static int leftChild(int i){
return 2 * i;
}
static int rightChild(int i){
return (2 * i) + 1;
}
}
}