Introduction to Heap Sort

Introduction:

Heap sort is one of the best algorithm which is widely used sorting technique in the data analytics.But why??? “ Because due to it’s time complexity and flexibility”.I will explain the time complexity no worries :),Let’s start.

Why we are need Complete Binary Tree??

I think all of you know about the Binary Tree very well and also you must know about the types of binary trees as well.

1. Binary Search Tree
2. Complete Binary Tree
3. Almost Complete Binary Tree
4. Skew Binary Tree — (Left Skew and Right Skew)

Complete Binary Tree:

A complete binary tree is a binary tree in which all the levels are completely filled except possibly the lowest one, which is filled from the left. A complete binary tree is just like a full binary tree, but with two major differences. All the leaf elements must lean towards the left.

Heap Data-Structure is logically designed on Complete Binary Tree or Almost Complete Binary Tree ,wait wait what is Exactly means heap .

What is a Heap??

Heap is a Data-Structure which is vastly used in today’s modern world why it so because the today’s computers Main Memory consists of Stack and Heap data structures.

Representation of Heap

Heap can be represented as arrays and trees.

After creating tree we can convert it into array,and all data manipulation is done through arrays.

Heap Types :

Min Heap :

The value of parent node always less than it’s all child nodes.

Max Heap :

The value of parent node always greater than it’s all child nodes.

Heapify— (Faster Method for creating Min or Max heap)

Heapify is the process of creating a heap data structure from a binary tree. It is used to create a Min-Heap or a Max-Heap. Let the input array be Initial Array. Create a complete binary tree from the array Complete binary tree. Start from the first index of non-leaf node whose index is given by n/2–1

Note: “Remember we can only delete a node always at the root only in the heap.”

Heap Sort

So we have learnt about some basic concepts of heap , now let’s start the heap-sort.

Algorithm:

1. HeapSort(arr)
2. BuildMaxHeap(arr)
3. for i = length(arr) to 2
4. swap arr[1] with arr[i]
5. heap_size[arr] = heap_size[arr] ? 1
6. MaxHeapify(arr,1)
7. End

First step is Create a Max or Min Heap

Iterate through all nodes in respective heap.

delete the root node first and replace it with last node and perform the heapify method to rewind the condition of Complete Binary Tree.And add the deleted node at the last.

Let’s Visualize the Heap Sort:

Time complexity

CaseTime Complexity

Best Case O(n logn)

Average Case O(n log n)

Worst Case O(n log n)