Heap Sorting method and algorithm

In heap sorting process:

First of all organizing the whole data to be sorted as a binary tree i.e. heap. And after that impletment heap sorting.

Step 1: (How to data organizing as binary tree?)

Remember only 2 rule:

Rule:1.

The parent node must be greater then child node.
If parent node is not greater then to child node not replace it with parent node. And if binary tree is large then, if relaceing child node(now its parent node) is greater then to great-parent node then its also is replace the great-parent node.

Rule:2.

New element always insert in left side and after right side of parent node.
If left side of parent element has already element then new element would be insert in right side. And if right side of parent node has already element then new element will be insert in left side.

Step 2: (How to perform heap sorting:)

Remove the topmost element(largest element) and replace it with the rightmost element.

Step 3:

Repeat steps 1 and 2 untill all elements is not sorted.

Heap Sorting method/process by example:

max heap : 80 , 32 , 31 , 110 , 50 , 40 , 120 

Step1:
                  80

Step2:  
                 80
              /      \
           32        31

Step3:  
                 80                           80                         110
              /       \                      /     \                     /       \
           32         31    ==>     110       31     ==>    80         31
          /                             /                            /
     110                           32                          32


Step4:
                 110
               /      \
            80        31
          /    \        
      32       5


Step5:
                  110                               110
                /       \                          /      \
             80         31    ==>          80        40
           /    \       /                     /   \       / 
        32      50   40                32      50   31



        
Step6:
                 110                               110                                120
               /       \                          /        \                           /       \
           80         40       ==>        80          120      ==>        80         110
         /     \      /    \                /    \        /    \                 /    \      /    \
     32       50   31   120         32     50    31     40           32     50  31       40


-------------------------------------------------------------------------------------

(1)
                  120 [1]
                 
              /                 \

          80 [2]               110 [3]

      /         \              /           \

 32 [4]       50 [5]     31 [6]         40 [7]

// [1],[2],[3],[4],[5],[6],[7]: Index number 
// Now applying step 2(perform heap sorting)
// Replace the topmost element with the rightmost element.

(2)
             40                                     110      
           /      \             Heaping        /       \
        80       110        =====>     80          40
      /   \       /    \                     /    \       /    \
   32     50   31    120              32     50   31    120

(3)
//now replace 110 with rightmost element i.e. 31 because 120 had been sorted.

            31                                        80                                 80
         /       \           Heaping             /       \        Heaping         /      \
       80        40        ======>        31         40      ======>    50       40
     /    \     /    \                         /     \      /    \                   /    \     /   \
   32   50  110   120                  32     50   110    120           32    31  110  120

(4)
//now replace 80 with rightmost element i.e. 31 because 110, 120 had been sorted.

           31                                           50                                    50
         /      \             Heaping              /        \           Heaping         /     \
       50       40          ======>         31          40        ======>    32      40
      /    \      /   \                           /     \       /     \                   /    \     /     \
   32     80  110  120                    32     80     110    120           31     80  110   120

(5)
//now replace 50 with rightmost element i.e. 31 because 80, 110, 120 had been sorted. 

              31                                      40
           /        \            Heaping         /       \
       32           40        ======>    32         31
     /     \        /    \                     /    \     /     \
   50     80    110    120             50     80  110    120

(6)
//now replace 40 with rightmost element i.e. 31 because 50, 80, 110, 120 had been sorted. 


              31                                     32
            /     \           Heaping            /     \
         32      40        ======>        31       40
       /    \     /    \                       /    \     /    \
    50   80   110   120               50    80   110    120

(7)
//now replace 32 with rightmost element i.e. 31 because 40, 50, 80, 110, 120 had been sorted. 

                   31
                /       \
            32        40
         /     \       /      \
     50     80   110    120

Now all elements are sorted: 31 , 32 , 40 , 50 , 80 , 110 , 120

Related programs:

1. Merge sorting
2. Heap sorting
3. Bubble sorting
4. Selection Sorting
5. Insertion sorting
6. Insertion sorting using function
7. Shell sorting
8. Quick sorting
9. Radix sorting
10. Liner sorting