Heapsort C# Tutorial


Heap Sort is another sorting algorithm that is comparison based and is part of the selection sort group of algorithms. In terms of performance, it has the same O(n * log n) time complexity and is close to being as efficient as the Quick Sort and Merge Sort, however, it is a bit slower. It is also like the Insertion Sort in that sorting is done in place (a constant space of O(1)), so no additional space is needed in order to sort. Unlike Merge Sort, it is not stable.

When to use Heap Sort

The C Version of Heap Sort

The C++ Version of Heap Sort

The Java Version of Heap Sort

The algorithm is as follows:

HEAPSORT(A), where A is an array

1.  BUILD-HEAP(A)

2.  for i = length[A], i >= 0, decrement i

3.  do exchange A[1]  A[i]

4.  heap-size[A]  heap-size[A] -1

5.  HEAPIFY(A, 1)

More in depth:

1. Start by building a heap
2. Once the heap is constructed, the element in the first position of the array will be the maximum and can be swapped into its correct position. That swap disrupts the heap, but it can be rebuilt by looking at a small portion of the elements in the array using the “heapify” procedure.

The heapsort algorithm starts by using BUILDHEAP to build a heap on the input array A[1 . . n], where n = length[A]. Since the maximum element of the array is stored at the root A[1], it can be put into its correct final position by exchanging it with A[n]. If node n is now “discarded” from the heap (by decrementing heap-size[A]), it is evident that A[1 . . (n – 1)] can be easily made into a heap. The children of the root remain heaps, but the new root element may violate the heap property. In order to restore the heap property, one call to HEAPIFY(A, 1) leaves a heap in A[1 . . (n – 1)]. The heapsort algorithm then repeats this process for the heap of size n – 1 down to a heap of size 2.

The runtime for Heapsort is O(n * log n). BuildHeap(A) has O(n) runtime time, and the Heapify(A,1) process is logarithmic, so O(log n), and combined produces the O(n * log n) runtime. For the best, average, and worst cases, Heap Sort guarantees O(n * log n) performance. Again, while it is slower than both Quick Sort and Merge Sort, Heap Sort guarantees in the worst case, logarithmic time.

There are a few parts to implementing this algorithm:

The heap

  • The heap is essentially an array that is represented/viewed as a binary tree structure, however, this binary tree structure is partially unsorted.
  • Remember that a heap is another way to represent a priority queue
  • A heap needs to be made in order to implement Heap Sort
  • The heap can be built recursively using this method
    • BUILD-HEAP(A)

      1. heap-size[A] <- length[A]

      2. for i <- length[A]/2 downto 1

      3. do HEAPIFY(A, i)

The Sorting

The overall sorting method that heapsort does occurs in the Heapify method. Heapify is used to restore the heap property of the array. This method can be written using the following pseudo-code:

HEAPIFY(A, i)

1 l <- LEFT(i)

2 r <- RIGHT(i)

3 largest = i

4 if l <= heap-size[A] and A[l] > A[i]

5 then largest <- l

6 else largest <- i

7 if r <= heap-size[A] and A[r] > A[largest]

8 then largest <- r

9 if largest != i

10 then SWAP A[i] <- A[largest]

11 HEAPIFY(A,largest)

Implementation in C#

    class Program
    {
        static void Main(string[] args)
        {
            int[] arr = { 10, 64, 7, 52, 32, 18, 2, 48};
            HeapSort hs = new HeapSort();
            hs.PerformHeapSort(arr);
            Console.ReadLine();
        }
    }
    class HeapSort
    {
        private int heapSize;

        private void BuildHeap(int[] arr)
        {
            heapSize = arr.Length-1;
            for (int i = heapSize/2; i >= 0; i--)
            {
                Heapify(arr, i);
            }
        }

        private void Swap(int[] arr, int x, int y)//function to swap elements
        {
            int temp = arr[x];
            arr[x] = arr[y];
            arr[y] = temp;
        }
        private void Heapify(int[] arr, int index)
        {
            int left = 2 * index;
            int right = 2 * index + 1;
            int largest = index;

            if (left <= heapSize && arr[left] > arr[index])
            {
                largest = left;
            }

            if (right <= heapSize && arr[right] > arr[largest])
            {
                largest = right;
            }

            if (largest != index)
            {
                Swap(arr, index, largest);
                Heapify(arr, largest);
            }
        }
        public void PerformHeapSort(int[] arr)
        {
            BuildHeap(arr);
            for (int i = arr.Length-1; i >= 0; i--)
            {
                Swap(arr, 0, i);
                heapSize--;
                Heapify(arr, 0);
            }
            DisplayArray(arr);
        }
        private void DisplayArray(int[] arr)
        {
            for (int i = 0; i < arr.Length; i++)
            { Console.Write("[{0}]", arr[i]); }
        }
    }

Depiction of a Heap structure

Depiction of a Heap structure

Heap representation using an array

Heap Sort Animation

Graph analysis of Heap Sort.

Heap Sort Interactive Demo

Advertisements

One thought on “Heapsort C# Tutorial

  1. Pingback: The Heap Data Structure (C++, Java, C#) | Bits and Pieces of Code

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