Make the frequent cases fast and the rare case correct

C# – Heapsort implementation with in-place cascade down

Heapsort is a comparison-based sorting algorithm to create a sorted array (or list), and is part of the selection sort family. Although somewhat slower in practice on most machines than a well implemented quicksort, it has the advantage of a more favorable worst-case O(n log n) runtime. Heapsort is an in-place algorithm, but is not a stable sort.- Wikipedia

In my previous article i have explained :

1 . BUILD-MAX-HEAP – runs in linear time, resultant max-heap from an unordered input array.
2 . MAX-HEAPIFY – maintains heap property and runs in O(lg n) time.
3 . MAX-HEAP-INSERT – O(lg n)
4 . HEAP-EXTRACT-MAX – O(lg n)
5 . HEAP-INCREASE-DECREASE-KEY – O(lg n) //not needed for heapsort

The function of heapsort is to insert all the unordered items into a heap using the normal Insert() from the previous article and repeatedly using Remove() will then remove the items in sorted order.

The HEAPSORT procedure takes time O(n lg n), since the call to BUILD_HEAP takes time O(n) and each of the n -1 calls to Heapify takes time O(lg n).

Heapsort competes with Mergesort as both have worst case O(nlg n) however a well implemented quicksort is better than heapsort since the while loop in the CascadeDown() has more operations which drag the performance as compared to few operations in a quicksort.

To improve heapsort performance a little more

For Time efficiency:
we can replace the Insert() and Remove() function which take O(n) by a single function called CascadeDown(). When we build a heap from an unordered array the elements from N/2 – 1 to n correspond to the nodes on the bottom row i.e those with no children and these are already correct heaps, because they are trees with only one node;we don’t need to apply CascadeDown() to these nodes. We can start at node N/2-1, the rightmost node with children to Cascade. Thus, we need only half as many Cascade operations.

This way we save some time.

For space efficiency:
We can use the same unordered array to store the removed elements. As the max node is removed it can be placed into the last position in the array as the elements would have shifted by one index towards the start of the array.

This improvement could make considerable difference on large data and thus heapsort O(nlg n) run time is better than O(n2) of a quicksort.

Implementation : Note getting rid of Insert() and Remove() functions.

using System;
using System.Collections.Generic;
using System.Text;
using System.IO;

namespace HeapSort
    class Node
        private int nodeItem;
        public Node(int value)
        { nodeItem = value; }
        public int getvalue()
        { return nodeItem; }
        public void setvalue(int id)
        { nodeItem = id; }

    class Heap
        private Node[] heapArray;
        private int maxSize;
        private int currentSize;
        public Heap(int maxHeapSize)
            maxSize = maxHeapSize;
            currentSize = 0;
            heapArray = new Node[maxSize];
        public bool IsEmpty()
        { return currentSize == 0; }

        public Node Remove() // Remove maximum value node
            Node root = heapArray[0];
            heapArray[0] = heapArray[--currentSize];
            return root;
        public void CascadeDown(int index)
            int largerChild;
            Node top = heapArray[index]; 
            while (index < currentSize / 2) 
                int leftChild = 2 * index + 1;
                int rightChild = leftChild + 1;
                if (rightChild < currentSize && heapArray[leftChild].getvalue() < heapArray[rightChild].getvalue())
                    largerChild = rightChild;
                    largerChild = leftChild;
                if (top.getvalue() >= heapArray[largerChild].getvalue())
                heapArray[index] = heapArray[largerChild];
                index = largerChild; 
            heapArray[index] = top; 
        public void displayArray()
            for(int j=0; j<maxSize; j++)
                Console.Write(heapArray[j].getvalue() + " ");
        public void InsertAt(int index, Node newNode)
        { heapArray[index] = newNode; }
        public void setSize()
        { currentSize = 10; } // we have 10 elements
        public void DisplayHeap()
            Console.Write("Elements of the Heap Array are : ");
            for (int m = 0; m < currentSize; m++)
                if (heapArray[m] != null)
                    Console.Write(heapArray[m].getvalue() + " ");
                    Console.Write("-- ");
            int emptyLeaf = 32;
            int itemsPerRow = 1;
            int column = 0;
            int j = 0;
            String separator = "...............................";
            Console.WriteLine(separator + separator);
            while (currentSize > 0)
                if (column == 0)
                    for (int k = 0; k < emptyLeaf; k++)
                        Console.Write(' ');

                if (++j == currentSize)
                if (++column == itemsPerRow)
                    emptyLeaf /= 2;
                    itemsPerRow *= 2;
                    column = 0;
                    for (int k = 0; k < emptyLeaf * 2 - 2; k++)
                        Console.Write(' ');
            Console.WriteLine("\n" + separator + separator);
    class Program
        public static void Main(String[] args)
            int size = 10;
            Heap theHeap = new Heap(size);
            theHeap.InsertAt(0,new Node(40));
            theHeap.InsertAt(1,new Node(70));
            theHeap.InsertAt(2,new Node(20));
            theHeap.InsertAt(3,new Node(60));
            theHeap.InsertAt(4,new Node(50));
            theHeap.InsertAt(5,new Node(100));
            theHeap.InsertAt(6,new Node(82));
            theHeap.InsertAt(7,new Node(35));
            theHeap.InsertAt(8,new Node(90));
            theHeap.InsertAt(9,new Node(10));

            for(int j=size/2-1; j>=0; j--) 
            Console.Write("Heap: ");
            for(int j=size-1; j>=0; j--) 
            { // put the max value at end of array and so on ascending sort
                Node biggestNode = theHeap.Remove();
                theHeap.InsertAt(j, biggestNode);
            Console.Write("Sorted array is : ");


One response to “C# – Heapsort implementation with in-place cascade down

  1. Jayesh Panchal May 10, 2013 at 12:45 pm

    Nice Code Buddy…

    Check out my version of Heap Sort here

Leave a Reply

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

You are commenting using your 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: