Heap Sort

Heap sort is a sorting method on Binary Heap.

First things First

All you need to know about heap. 

1. Heap must be a Complete Binary Tree 
2. All trees are either Min Heap or Max Heap
3. Heap sort is an in-place sort algorithm
4. It is not very stable

Here I plan to construct Heap Sort Algorithm on a Min Heap.The Algorithm primarily has two main functions.

1. Heapify Function
2. Heap Sort Function

References from CLRS 

 Parent(i) 1 return(floor(i/2))

 Left (i)    1 return ( 2 * i + 1 )

 Right (i)  1 return ( 2 * i + 2 )

 Property for Max Heap 

    A[ Parent ] >= A[ i ]

 Property for Min Heap

     A[ Parent ] <= A[ i ]

Heapify Function

heapify(int arr[], int n, int i) largest=i l=2*i+1 r=2*i+2 if(l<n arr="" l="">arr[largest]) largest=l if(r<n arr="" r="">arr[largest]) largest=r if(largest!=i) swap(arr[i], arr[largest]) heapify(arr,i,largest)

Heap Sort Function

heapsort(int arr[], int n) for(int i=floor(n/2); i>=0;i--) heapify(arr,n,i) for(int i=n-1; i>=0;i--) swap(arr[0],arr[i]) heapify(arr,i,0)

Deletion of node is done at the root node after swapping it with the last node of the list. Deleting it takes O(1) time complexity.
Worst Case Time Complexity : O(n log n)
Space Complexity : O(n)
Source Code: HeapSort.cpp
References: StudyTonight

Naive Pattern Searching Algorithm

Naive Pattern Search algorithm as the name suggests is a very naive method of searching a pattern. The naive logic is to compare every instance of the pattern with every instance of the text.

Algorithm

for i in range 0 to N-M # Primary Comparison of the # Sample text with Pattern for j in range 0 to M; if text[i+j]!=pat[j] break; # Implies that j loop has traversed # to the last instance of the pattern, # and all comparisons are matching if(j==M) print("Instance found at:"i+1) Where N is the Length of the text and M is the Length of the pattern

Naive algorithm is not an optimized solution because the complexity is O(n^2). We need better and more optimized solutions.

Source Code: NaiveSearchAlgo