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.
Heap Sort in DS

Complexity table of Heap sort

ComplexityBest caseAverage caseWorst case
TimeO(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 sort program in java language

Output

Pin It on Pinterest

Share This