Heap Sort

Facebooktwitterredditpinterestlinkedinmailby feather

Heap Sort

A heap is a tree-based data structure that has specific properties.

  • Heap is always a complete binary tree (CBT). That is, all the nodes of the tree are completely filled.
  • If the value placed in each node is greater than or equal to its two children, then that heap is called max heap.
  • If the value placed in each node is less than or equal to its two children, then that heap is called min-heap.
  • If you want to sort the list in ascending order (increasing order), then you create the min-heap.
  • If you want to sort the list in descending order (decreasing order), then you create the max heap.

Complexity table of Heap sort

Complexity Best case Average case Worst case
Time O(nlogn) O(nlogn) O(nlogn)
Space     O(1)

Selection sort algorithm

This algorithm is for max heap sort.

Step 1: Create a new node.

Step 2: Assign a value to the node.

Step 3: Compare the value of the child node with the value of the parent node.

Step 4: If the child node value is greater than the parent node value, then interchange them. 

Step 5: Repeat steps 3 and 4 until the heap is sorted correctly.

Heap sort program in C language

Output

heap sorted elements 10 20 30 40 50 60 70 80 90 100  

Heap sort program in java language

Output

heap sorted elements 10 20 30 40 50 60 70 80 90 100  
Facebooktwitterredditpinterestlinkedinmailby feather