RSS

Heap Sort in C#

21 Aug

A simple Heap Sort implementation using C#.

public static void HeapSort(int[] input)
{
    //Build-Max-Heap
    int heapSize = input.Length;
    for (int p = (heapSize - 1) / 2; p >= 0; p--)
        MaxHeapify(input, heapSize, p);

    for (int i = input.Length - 1; i > 0; i--)
    {
        //Swap
        int temp = input[i];
        input[i] = input[0];
        input[0] = temp;

        heapSize--;
        MaxHeapify(input, heapSize, 0);
    }
}

private static void MaxHeapify(int[] input, int heapSize, int index)
{
    int left = (index + 1) * 2 - 1;
    int right = (index + 1) * 2;
    int largest = 0;

    if (left < heapSize && input[left] > input[index])
        largest = left;
    else
        largest = index;

    if (right < heapSize && input[right] > input[largest])
        largest = right;

    if (largest != index)
    {
        int temp = input[index];
        input[index] = input[largest];
        input[largest] = temp;

        MaxHeapify(input, heapSize, largest);
    }
}
Advertisements
 
8 Comments

Posted by on August 21, 2012 in Algorithm, C#

 

8 responses to “Heap Sort in C#

  1. Paul

    March 11, 2013 at 5:59 AM

    In MaxHeapify, line 05, did you mean int largest = index rather than largest = 0?

     
    • begeeben

      March 12, 2013 at 7:00 PM

      The purpose of line 05 is only to declare an int. The value of largest will be decided in line 7~10.

       
    • Paul

      May 2, 2016 at 8:49 AM

      yes.

      I just wrote a visual sorter. it hung when I sorted 2000 items. The largest needs to to initialized to index so it there will not be a swap at the end. It is possible to reach the end without being set

       
  2. Sergey Belousov

    May 28, 2013 at 11:38 AM

    Thank you very much! Finally found a working code )
    Subscribed to your blog

     
  3. Misha higer

    May 7, 2014 at 12:41 AM

    Thank you!!!

     
  4. C

    January 23, 2015 at 10:13 PM

    Amazing. Looking for a lot of algorithms to get acquainted with them and this was by far the simplest implementation of Heap sort that I came across!

     
  5. code down

    August 13, 2015 at 8:11 PM

    will this work for heapsize = 7
    in that case first for loop starts with p = 3, but it should start from p=2

    *(0)
    / \
    *(1) *(2)
    / \ / \
    *(3) *(4) *(5) *(6)

     
  6. Paul

    May 2, 2016 at 8:46 AM

    Hello,

    I think I found a bug in you code. I tested it.

    line 5 should be
    int largest = index;

    that makes it work.

     

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: