Heap Sort

Heap Sort is interesting because the use of the 'heapify' method that creates a binary tree as a flat array. First, a binary tree, also known as a heap, is created, and then the same function is used to sort the elements. In a heap, the first node in the array at zero (0) is the top node of the binary tree. The next two (2) items are the two (2) subnodes of the top node, and so on. For each node at a position (positionIndex), its 2 subnodes are in the following positions:

  • int left = 2 * positionIndex + 1;
  • int right = 2 *  positionIndex + 2;

The CommonMethods.Swap() function is a reusable class, since swapping values by position is a common action during these example sorts.

Class

using System;

namespace Algorithms
{
    class HeapSort
    {
        public int[]  Sort()
        {
            //creates array
            int[] arrayToSort = { 11, 1, 22, 2, 33, 3, 44, 4, 55, 5, 66, 6, 7, 77, 88 };
           
            //creates a heap
            BuildHeap(arrayToSort);

            //sorts a heap
            //takes the largest element @ first position and moves to end
            //reuses the same heapify function, but in reverse, to sort the array
            int size = arrayToSort.Length;
            for (int counter = size - 1; counter > 0; counter--)
            {
                CommonMethods.Swap(arrayToSort, 0, counter);
                HeapifyRecursive(arrayToSort, 0, counter);
            }
            return arrayToSort;
        }

        //a heap, in this case, is a binary tree
        //the largest element is in the first position
        //the next two positions are the 2 subelements of this node, and so on
        //it looks at each element, then reporders them so it maintains the heap structure
        public int[] BuildHeap(int[] arrayToSort)
        {
            int size = arrayToSort.Length;
            int start = (arrayToSort.Length / 2) - 1;
          
            for (int counter = start; counter >= 0; counter--)
            {
                HeapifyRecursive(arrayToSort, counter, size);
            }
            return arrayToSort;
        }

        public void HeapifyRecursive(int[] arrayToSort, int idx, int max)
        {
            int left = 2 * idx + 1;
            int right = 2 * idx + 2;
            int largest;
            if (left < max && arrayToSort[left] > arrayToSort[idx])
            {
                largest = left;
            }
            else
            {
                largest = idx;
            }

            if (right < max && arrayToSort[right] > arrayToSort[largest])
            {
                largest = right;
            }

            if (largest != idx)
            {
                CommonMethods.Swap(arrayToSort, idx, largest);
                HeapifyRecursive(arrayToSort, largest, max);
            }
        }
    }
}

Comments

  1. What about CommonMethods?

    ReplyDelete
  2. in which language did this code write? ı need counting, selection ,heap and bucket sort algoritms , in visual basic. please help me, in 5 days.

    ReplyDelete
  3. This code is C#, and you can take any of the code on this site and convert it via tools like Telerik's Code Convertor, at http://converter.telerik.com/

    ReplyDelete
    Replies
    1. sir james igoe?
      im trying to make a sorting program, about sorting an image pixel using heap sort i already made 50% of my program but i cant proceed because i dont know how to put the heap sort in my program i just want to sort the pixels of the image using heap sort .
      if you read this will help me how ?
      im just a beginner.
      thank you sir and more power

      Delete
  4. hello sir james i would like to ask you im hoping you will answer me back. i am making a sorting program which heap sort is my algorithm an i want to sort the pixel of an image to get the pixel is to multiply the dimension. i already made tht 50% of my program but i cant proceed because i dont know how to put the heapsort in my program i just want you to help me of how to sort the image pixel using heap sort algo.
    im a beginner hope you will answer back . thank you and more power

    ReplyDelete

Post a Comment

Popular posts from this blog

Do Algorithms Make You a Better Developer?

Bucket Sort