The following gives 5 lists of numbers in ascending order: List #1: 1, 2, 6. Lis

Question

The following gives 5 lists of numbers in ascending order:

List #1: 1, 2, 6.

List #2: 5, 7, 10, 12.

List #3: 3, 4.

List #4: 8, 9, 11, 14, 15.

List #5: 13, 16, 18, 20.

The goal is to use a minimizing heap to merge these 5 lists to obtain a single list in ascending order. We discussed an algorithm of complexity n.log(k) for merging k ordered lists with a total of n elements using a heap. Use this algorithm to obtain the first 8 numbers of the ordered list. Start with the following heap formed by the smallest (the first) element from each list, i.e., 1, 5, 3, 8, 13: A(1) =1, A(2) =3, A(3) =5, A(4) =8, A(5) = 13.

Explanation / Answer

#include<iostream>
#include<limits.h>
using namespace std;

#define n 4

struct MinHeapNode
{
int ele;
int i;
int j;
};

void swap(MinHeapNode *x, MinHeapNode *y);

class MinHeap
{
MinHeapNode *harr;
int heap_size;
public:

MinHeap(MinHeapNode a[], int size);

void MinHeapify(int );

int l(int i) { return (2*i + 1); }

int r(int i) { return (2*i + 2); }

MinHeapNode getMin() { return harr[0]; }

void replaceMin(MinHeapNode x) { harr[0] = x; MinHeapify(0); }
};

int *mergeKArrays(int arr[][n], int k)
{
int *output = new int[n*k];

MinHeapNode *harr = new MinHeapNode[k];
for (int i = 0; i < k; i++)
{
harr[i].ele = arr[i][0];
harr[i].i = i;
harr[i].j = 1;
}
MinHeap hp(harr, k);

for (int count = 0; count < n*k; count++)
{
MinHeapNode root = hp.getMin();
output[count] = root.ele;

if (root.j < n)
{
root.ele = arr[root.i][root.j];
root.j += 1;
}
else root.ele = INT_MAX;

hp.replaceMin(root);
}

return output;
}

MinHeap::MinHeap(MinHeapNode a[], int size)
{
heap_size = size;
harr = a;
int i = (heap_size - 1)/2;
while (i >= 0)
{
MinHeapify(i);
i--;
}
}

void MinHeap::MinHeapify(int i)
{
int l = l(i);
int r = r(i);
int smallest = i;
if (l < heap_size && harr[l].ele < harr[i].ele)
smallest = l;
if (r < heap_size && harr[r].ele < harr[smallest].ele)
smallest = r;
if (smallest != i)
{
swap(&harr[i], &harr[smallest]);
MinHeapify(smallest);
}
}

void swap(MinHeapNode *x, MinHeapNode *y)
{
MinHeapNode temp = *x; *x = *y; *y = temp;
}

void printArray(int arr[], int size)
{
for (int i=0; i < size; i++)
cout << arr[i] << " ";
}

int main()
{
int arr[][n] ={{1,2,6}{5,7,10,12}{3,4};{8,9,11,14,15}{13,16,18,20}};
int k = sizeof(arr)/sizeof(arr[0]);

int *output = mergeKArrays(arr, k);

cout << "Merged array is " << endl;
printArray(output, n*k);

return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.