Heap Introduction

Heap :

A Heap is a binary tree where all the leaves are either present at depth d or d-1 same as complete binary tree.
for every node n, the value in n is greater than or equal to the values in its children, thus also greater or equal
to all of the values in its subtrees.

Conditions for Heap: 
1) All leaves are either at depth d or d-1 for same d value
2) All of the leaves at depth d-1 are to the right of the leaves at d depth.
3) There is at most 1 node with just 1 child, that child is the left of its parent and it is the rightmost leaf at depth d.

examples  from http://pages.cs.wisc.edu/~vernon/cs367/notes/11.PRIORITY-Q.html

Linked List rearrangement Example 1

/* re-arrange nodes in the LL inplace as below
head : 1->2->3->4->5
output: 1->5->2->4->3
 */

#include<stdio.h>
#include<stdlib.h>
typedef struct Node
{
    int num;
    struct Node *next;
} Node;

Node *newNode(int num)
{
    Node *temp = (Node*) malloc(sizeof(Node));
    temp->num = num;
    temp->next = NULL;
    return temp;
}

void reverse (Node** head)
{
    Node *prev = NULL,  *cur = *head, *next;
    while(cur) {
    next = cur->next;
    cur->next = prev;
    prev = cur;
    cur = next;
    }
    *head = prev;
}

void reArrangeNodes( Node** head)
{
    Node *slow = *head;
    Node *fast = slow->next;
    // find the mid point
    while (fast && fast->next) {
    slow = slow->next;
    fast = fast->next->next;
    }
    Node *head1 = *head;
    Node *head2 = slow->next;
    slow->next = NULL;

    reverse(&head2);
    *head = newNode(0);
    Node* cur = *head;
    while(head1 || head2) {
    if (head1) {
        cur->next = head1;
        cur = cur->next;
        head1 = head1->next;
    }

    if (head2) {
        cur->next = head2;
        cur = cur->next;
        head2 = head2->next;
    }
    }
    *head = (*head)->next;
}
int main()
{
    Node *head = newNode(1);
    head->next = newNode(2);
    head->next->next = newNode(3);
    head->next->next->next = newNode(4);
    head->next->next->next->next = newNode(5);
    head->next->next->next->next->next = newNode(6);
    head->next->next->next->next->next = newNode(7);
    printf("Input: ");
    Node *temp = head;
    while(temp) {
    printf ("%d ", temp->num);
    temp = temp->next;
    }
    printf("\n");
    reArrangeNodes(&head);
    printf("output: ");
    while(head) {
    printf("%d ", head->num);
    head=head->next;
    }
    printf("\n");
    return 0;
}

compare two string represented as Linked List similar to strcmp

/* compare two string represented as LL similar to strcmp */

#include<stdio.h>
#include<stdlib.h>
typedef struct Node
{
  char c;
  struct Node *next;
}Node;

Node* newNode(char c)
{
  Node *temp = (Node*) malloc (sizeof(Node));
  temp->c = c;
  temp->next = NULL;
  return temp;
};

int compare( Node *list1, Node *list2)
{
  while (list1 && list2 && (list1->c == list2->c))
      {
        list1 = list1->next;
        list2 = list2->next;
      }

   if (list1 && list2)
      return (list1->c >  list2->c) ? 1 : -1;

   if (list1 && !list2)
      return 1;
   if (!list1 && list2)
       return -1;
   return 0;
}

int main()
{
  Node *list1 = newNode('p');
  list1->next = newNode('e');
  list1->next->next = newNode('a');
  list1->next->next->next = newNode('c');

  Node *list2 = newNode('p');
  list2->next = newNode('e');
  list2->next->next = newNode('a');
  list2->next->next->next = newNode('c');
  list2->next->next->next->next = newNode('e');
  printf("compare result %d\n", compare(list1, list2));
  return 0;
}

remove all duplicates from the input string

/* remove all duplicates from the input string */

#include<stdio.h>
void removeDup(char *str) {
    int str_hash[256] ={0};
    int i;
    int count = 0;
    for (i=0; str[i] != '\0'; i++)
    {
    str_hash[str[i]]++;
        if (str_hash[str[i]] == 1)
            str[count++] = str[i];
    }
    str[count] = '\0';
}

int main() {
    char str[]= "pppppeeeeeeeeeeaaaaaaaaaaaccccccceeeeeee";
    removeDup(str);
    printf("the result string is %s\n", str);
    return 0;
}

remove spaces from a given string

/* remove spaces from a given string */

#include <stdio.h>
void removeSpaces(char *str)
{
 int count =0;
 int i;
 for (i =0; str[i] != '\0';i++){
      if(str[i] != ' ')
         str[count++]=str[i];
 }
 str[count] = '\0';
}
int main()
{
 char str[] = "A    w   eso m  e  ";
 removeSpaces(str);
 printf("result string is %s\n", str);
 return 0;
}

Given an array A[] and a number x, check for pair in A[] with sum as x

/* Given an array A[] and a number x, check for pair in A[] with sum as x */

#include <stdio.h>
void quickSort(int*, int, int);
void printSumPair(int A[], int arr_size, int sum) {
    int l, r;
    // sort in increasing order
    quickSort(A, 0, arr_size - 1);
    l = 0;
    r = arr_size-1;
    while (l < r) {
        if (A[l] + A[r] > sum)
            r --;
        else if (A[l] + A[r] < sum)
            l++;
        else {
            printf("%d + %d equals %d\n", A[l], A[r], sum);
            break;
        }
    }
}

int main() {
    int arr[] = {1,4,45,6,10,8};  // sorted would be : {1,4,6,8,10,45}
    int x = 16;
    int arr_size = sizeof(arr)/sizeof(arr[0]);
    printSumPair(arr, arr_size, x);
    return 0;
}

void exchange (int *a, int *b) {
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

int partition (int A[], int si, int ei ) {
    int x  = A[ei];
    int i = si - 1;
    int j;
    for (j = si; j <= ei - 1; j++) {
       if(A[j] <= x) {
         i++;
         exchange (&A[j], &A[i]);
       }
    }
    exchange (&A[i+1], &A[ei]);
    return (i+1);
}

void quickSort (int A[], int si, int ei) {
    int pi;
    if (si < ei ) {
       pi = partition(A, si, ei);
       quickSort(A, si, pi-1);
       quickSort(A, pi+1, ei);
    }
}

if binary representation of a given number is pallindrom or not

/*  test if binary representation of a given number is pallindrom */

#include<stdio.h>
#include <stdbool.h>
bool isBinPallindrom(unsigned int num) {
    if (num == 0)
       return true;
    int posL = 1;
    int posR = 1;
    int temp = num;
    while(temp>>1) {
        temp >>=1;
        posR++;
    }
    printf("num is %d, MSB pos %d\n", num, posR);
    while (posR > posL) {
        if (((num & (1 << (posR -1))) >> (posR -1)) != ((num & (1 << (posL -1))) >> (posL -1))) {
              printf ("not pallindrom\n");
              return false;
        }
        posL++;
        posR--;
    }
    return true;
}
int main()
{
    unsigned int x = 22;
    printf("The number %d is %s\n", x, isBinPallindrom(x) ? "pallindrom": "not pallindrom");
    x = 0xFF;
    printf("The number %d is %s\n", x, isBinPallindrom(x) ? "pallindrom": "not pallindrom");
    return 0;
}