What is Heap Sort in DAA | Algorithm | Complexity

 What is Heap Sort? | Algorithm | Complexity

What is Heap Sort in DAA

---> In this blog we will see "What is Heap Sort" where we discuss all about Heap Sort in Theoretical part and also its Algorithm and Complexity.

----> Heap Sort is a sorting technique which is comes under the concept of the Data Structure and Design of Algorithm and Analysis (DAA) which is part of a tree and the sort program. In the Heap Sort it is all about array sorting or sorting from unsorted array which uses the tree feature which is an acyclic in nature, here we process the path at minimum distance or a minimum cost node.

---> In The Heap Sort it contain the following ,namely

• Root Node
• Parent Node
• Child / Leaf Node              

1) Root Node: - Root node is the node in which it get start to form the basic and first form of the tree kind                                structure.

2) Parent Node:- Parent Node represents the node having the number of nodes attached or having the                                 successors of that node.

3)Child / Leaf Node:- Child / Leaf Node represents of having no successor node which get them any other                                reference like parent node. or in other word it is determind as the ending node in the tree .

Algorithm:-

----> Procedure Heap_Sort(A)
        Build = MAx-Heap(A)
        for i = A Length down to 2
        exchange A[1] with A[i]
        A.heapsize = A.heapsize-1
       MAX - Heapify(A,i)
       return

       Build - Max Heap(A)
       A - heapsize = A Length
       for i = [A.length/2] down to 1

       max - Heapify [A,i]

       

       max - Heapify[A,i]

       l = left(i)

       r = right(i)

       

       if (l <=A.heapsize and A[1] >A[i])

            largest = 1

      else

             largest = i

      

      if (r <=A.heapsize & A[r] > A[largest])

             largest = r
     if largest != i

            exchange A[i] with A[largest]

            Max - Heapify (A,largest)

Complexity:- 

---> Heap Sort is basically a "Divide and Conquer" Strategy so its complexity is O(n log n)

Example with Steps:- 

                Array = [ 4 , 8 , 20 , 17 , 7 , 25 , 2 ,13 , 5 ]

Solution:-

Step 1: First arrange the array in the tree format as shown,

 

Step 2:- Replace or change the place of the root node with the largest number from child node as                          shown in figure

Step 3 :- Repeat the step 2 until all sort .....

Step 4: Mark the border at the sorted tree....

Retrieving of element from heap:

                      

Step 1: In this retrieving of element is of removing the element from the tree one by one and place in the array format where it is in the sorted manner...

For more detail click:-  1) Heap_Sort by gog.

                                      2) Heap_sort by tutorialspoint