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);
}
}
Daily Archives: September 14, 2014
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 2h -1 nodes.
- minimum number of nodes possible in a heap of height h is 2h.
- maximum number of nodes is 2h+1 -1 nodes.
Four basic procedures on heap are
- Heapify, which runs in O(log n) time.
- Build-Heap, which runs in linear time.
- Heap Sort, which runs in O(n log n) time.
- 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)
Median of the two sorted arrays of different sizes
Overall run time complexity should be O(log (m+n)).
int find_kth(int a[], int b[], int size_a, int size_b, int k)
{
if(size_a > size_b)
return find_kth(b, a, size_b, size_a, k);
if(size_a == 0)
return b[k-1];
if(k ==1)
return min(a[0], b[0]);
// K should be less than the size of array
int i = min(size_a, k/2);
int j = min(size_b, k/2);
if(a[i-1] > b[j-1])
// Now we need to find only K-j th element
return find_kth(a, b+j, size_a, size_b -j, k-j);
else
return find_kth(a+i, b, size_a-i, size_b, k-i);
return -1;
}
int find_median(int a[], int b[], int size_a, int size_b)
{
int left = (size_a + size_b +1)/2;
int right = (size_a + size_b +2)/2;
return ((find_kth(a,b, size_a,size_b, left) +
find_kth(a,b, size_a,size_b, right))/2);
}
Median of two sorted arrays of same size
Algorithm
- If length of both arrays is 1, take average and return the value.
- If length of both arrays is 2, then return following value (max(array1[0], array2[0]) + min(array1[1], array2[1]) )/2
- If length is greater than 2, follow steps below
- Find median of array1 and array2 individually. Let them be M1 and M2
- If M1 == M2 return M1
- If M1 < M2 follow step 1 onwards with array1[mid…N] and array2[0, mid-1]
- If M2 < M1 follow step 1 onwards with array2[mid…N] and array1[0, mid-1]
int getMedian(int ar1[], int ar2[], int n)
{
int m1;
int m2;
if (n == 1)
return (ar1[0] + ar2[0])/2;
if (n == 2)
return (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1])) / 2;
m1 = median(ar1, n);
m2 = median(ar2, n);
if (m1 == m2)
return m1;
/* if m1 < m2 then median must exist in ar1[m1....] and ar2[....m2] */
if (m1 < m2)
{
if (n % 2 == 0)
//If no. of elements are even, then do not include the middle element in next step
return getMedian(ar1 + n/2 - 1, ar2, n - n/2 +1);
else
//If no. of elements are odd, then include the middle element in next step
return getMedian(ar1 + n/2, ar2, n - n/2);
}
/* if m1 > m2 then median must exist in ar1[....m1] and ar2[m2...] */
else
{
if (n % 2 == 0)
return getMedian(ar2 + n/2 - 1, ar1, n - n/2 + 1);
else
return getMedian(ar2 + n/2, ar1, n - n/2);
}
}
/* Function to get median of a sorted array */
int median(int arr[], int n)
{
if (n%2 == 0)
return (arr[n/2] + arr[n/2-1])/2;
else
return arr[n/2];
}
Fixed Point in a given sorted array
Fixed Point in an array is an index i such that arr[i] is equal to i
int binarySearch(int arr[], int low, int high)
{
if(high >= low)
{
int mid = (low + high)/2;
if(mid == arr[mid])
return mid;
if(mid > arr[mid])
return binarySearch(arr, (mid + 1), high);
else
return binarySearch(arr, low, (mid -1));
}
return -1;
}
Find index of a peak element
int findPeakUtil(int arr[], int low, int high, int n)
{
int mid = (low + high)/2;
if ((mid == 0 || arr[mid-1] <= arr[mid]) &&
(mid == n-1 || arr[mid+1] <= arr[mid]))
return mid;
else if (mid > 0 && arr[mid-1] > arr[mid])
return findPeakUtil(arr, low, (mid -1), n);
else return findPeakUtil(arr, (mid + 1), high, n);
}
Learn By Coding 