Remove duplicate from sorted linked list

struct node {
    int data;
    struct node* next;
};
 
void removeDuplicates (struct node* head)
{
   struct node* current = head;
   struct node* next_next; 
   
   if(current == NULL) 
      return; 
 
   while(current->next != NULL){
      if(current->data == current->next->data) 
      {
          next_next = current->next->next;
          free(current->next);
          current->next = next_next;  
       }
       else{
          current = current->next; 
       }
   }
}

Delete element from Linked List

struct node {
    int data;
    struct node *next;
};
 
void deleteNode(struct node *head, struct node *n)
{
    if(head == n)
    {
        if(head->next == NULL){
            return;
        }

        // Node to be deleted is head
        head->data = head->next->data;
        n = head->next;
        head->next = head->next->next;
        free(n);
    }
 
    // When not first node
    struct node *prev = head;
    while(prev->next != NULL && prev->next != n)
        prev = prev->next;
  
    prev->next = prev->next->next;
    free(n);
}

Reverse Linkedlist

Static void reverse (struct node *head){
    Node *prev = NULL;
    Node *current = *head;
    Node *next;

    While (current !=NULL){
         next = current -> next;
         current ->next = prev;
         prev = current;
         current = next;
     }
*head = prev;
}

Add element in Linked List

struct node
{
    int data;
    struct node *link;
} *head;

void add_beginning (int num) {
    struct node *temp;
    temp = (struct node *)malloc(sizeof(struct node));
    temp ->data = num;
    temp ->link = NULL;

    if (head == NULL) {
        head = temp;
   }
   else {
       temp ->link = head;
       head = temp;
   }
}

void add_end (int num) {
    struct node *temp;
    temp = (struct node *)malloc(sizeof(struct node));
    temp ->data = num;
    temp ->link = NULL;

    if (head == NULL){
          head = temp;
    }
    else {
         right = (struct node *)head;
         while(right ->link != NULL)
              right = right ->link;
         right ->link = temp;
    }
}         

Void add_middle (int c, int num){
    struct node *temp;
    temp = (struct node *)malloc(sizeof(struct node));
    temp ->data = num;
    temp ->link = NULL;
   
     if (head == NULL){
          head = temp;
    }
    else {
        struct node *right, *right1;
        right = head;
         right1 = head;
         for (int i = 0; i <c; i++)
             right = right ->link;
           
       right1 = right ->next;
       right ->next = temp;
       temp ->next = right1;
     } 
 }

Heap Sort

void swap(int *a, int *b)
{
    *a = *a + *b;
    *b = *a - *b;
    *a = *a - *b;
}
      
void minHeapify(int a[], int size, int i)
{
    int l = 2*i + 1; //using zero based arrays
    int r = 2*i + 2;
    int smallest = i;
    if(l<size && a[l]<a[smallest])
       smallest = l;
     if(r<size && a[r]<a[smallest])
       smallest = r;
     if(smallest!=i)
     {
         swap(&a[i],&a[smallest]);
         minHeapify(a,size,smallest);
     }        
 }
        
  void buildMinHeap(int a[], int size) {
        for(int i=size/2;i>=0;i--)
            minHeapify(a,size,i);           
}
   
  void heapsort (int a[], int size)
  {      
      buildMinHeap(a,size);     
      while (size > 1)
      {
          swap(&a[0], &ma[size - 1]);
          -- size;  
          minHeapify(a,size,0);
       }      
   }

void removeMin(int a[], int size) 
{ 
    if (isEmpty()) 
         throw new HeapException("Heap is empty"); 
    else { 
         a[0] = a[size - 1]; 
         size--; 
         if (heapSize > 0) 
             minHeapify(a,size,0);
         } 
  }

Find k largest(or smallest) elements in an array. No sorting allowed

Min Heap method

• Build a Min Heap of the first k elements (arr[0] to arr[k-1]) of the given array. O(k)
• For each element, after the kth element (arr[k] to arr[n-1]), compare it with root of min heap.
  If the element is greater than the root then make it root and call heapify for min heap.
  else ignore it. O((n-k)*logk)
• Finally, min heap has k largest elements and root of the min heap is the kth largest element.
  O(k + (n-k)Logk) without sorted output.
• If sorted output is needed then O(k + (n-k)Logk + kLogk)

void swap(int *a, int *b)
    {
        *a = *a + *b;
        *b = *a - *b;
        *a = *a - *b;
    }
      
    void minHeapify(int a[], int size, int i)
    {
        int l = 2*i + 1; //using zero based arrays
        int r = 2*i + 2;
        int smallest = i;
        if(l<size && a[l]<a[smallest])
            smallest = l;
        if(r<size && a[r]<a[smallest])
            smallest = r;
        if(smallest!=i)
        {
            swap(&a[i],&a[smallest]);
            minHeapify(a,size,smallest);
        }   
    }
       
    void buildMinHeap(int a[], int size) {
        for(int i=size/2;i>=0;i--)
            minHeapify(a,size,i);  
    }
       
    int kthLargest(int a[], int size, int k)
    {
        int minHeap[k];
        int i;
        for(i=0;i<k;i++)
            minHeap[i] = a[i];
        
        buildMinHeap(minHeap,k);
        for(i=k;i<size;i++)
        {
            if(a[i]>minHeap[0])
            {
                minHeap[0]=a[i];
                minHeapify(minHeap,k,0);
            }
        }
        return minHeap[0];
    }

Heap Tree

A Binary Heap is a Complete Binary Tree where items are stored in a special order such that value in a parent node is greater(or smaller) than the values in its two children nodes. The former is called as max heap and the latter is called min heap.

A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

PARENT (i)
return floor(i/2)
LEFT (i)
return 2i
RIGHT (i)
return 2i + 1

Heap of height h

• The levels above the lowest level form a complete binary tree of height h -1 and 2^h -1 nodes.
• minimum number of nodes possible in a heap of height h is 2^h.
• maximum number of nodes is 2^h+1 -1 nodes.

Four basic procedures on heap are

1. Heapify, which runs in O(log n) time.
2. Build-Heap, which runs in linear time.
3. Heap Sort, which runs in O(n log n) time.
4. Extract-Max, which runs in O(log n) time

Insertion Sort

void insertionSort(int arr[], int n)
{
   int i, key, j;
   for (i = 1; i < n; i++)
   {
       key = arr[i];
       j = i-1;
 
       /* Move elements of arr[0..i-1], that are
          greater than key, to one position ahead
          of their current position */
       while (j >= 0 && arr[j] > key)
       {
           arr[j+1] = arr[j];
           j = j-1;
       }
       arr[j+1] = key;
   }
}

Time Complexity: O(n*n)

Uses: Insertion sort is uses when number of elements is small. It can also be useful when 
input array is almost sorted, only few elements are misplaced in complete big array.

Bubble sort

void bubbleSort(int arr[], int n)
{
   int i, j;
   bool swapped;
   for (i = 0; i < n; i++)
   {
     swapped = false;
     for (j = 0; j < n-i-1; j++)
     {
        if (arr[j] > arr[j+1])
        {
           swap(&arr[j], &arr[j+1]);
           swapped = true;
        }
     }
 
     // IF no two elements were swapped by inner loop, then break
     if (swapped == false)
        break;
   }
}

void swap(int *xp, int *yp)
{
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}

Time Complexity: O(n*n)

Selection sort

The selection sort algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning.

void swap(int *xp, int *yp)
{
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}
 
void selectionSort(int arr[], int n)
{
    int i, j, min_index;
 
    // One by one move boundary of unsorted subarray
    for (i = 0; i < n-1; i++)
    {
        // Find the minimum element in unsorted array
        min_index = i;
        for (j = i+1; j < n; j++)
          if (arr[j] < arr[min_index])
            min_index = j;
 
        // Swap the found minimum element with the first element
        swap(&arr[min_index], &arr[i]);
    }
}

Time Complexity: O(n*n)