Question

Write a program in either C++ or Java meeting these requirements Description: In this program, we assume that our data comes in dynamically. We need to maintain our data in a heap, after every insertion and deletion. We also need to handle the underlying array dynamically. whenever we detect an overflow in our array, we will create a new array with size doubling the previous size. Requirements: 1. (Dynamic Data) when we generate the data, we simulate dynamic data. We use a 2000-element integer array containing 2000 random integers with values between 1 and 2000 inclusive.But we do not generate them at the same time. Every time we generate 100 random integers. 2. (Initial array) when our data grows, we need to change the array size if an over- flow is detected. Initially, create an array with size 100 to hold the first 100 random integers. Then build a heap immediately. (You have the flexibility for your initial array size. For example, in a heap, we do not store data in the first element. You can use an array with 101 elements.) 3. (Copy data) Before you insert a new integer into the array, check if there would be an overflow if the number is inserted. If yes, create a new array with size doubling the previous size and copy data from the old array to the new array, then insert the new integer. 4. (Recover heap) After every data insertion, fix the heap immediately. 5. (Heapsort ) At the end when all the data comes in, apply the heapsort on the heap. 6. (Display information) Every time when you generate 100 random integers, print them out on the screen with 20 numbers per lineEvery time when you double the array size, print out the sizes before and after the change. At the end, print out the sorted array.

Answer 1

Complete code of soution in c++ Programming language:-

#include<bits/stdc++.h>

using namespace std;

// Heapify function to reserve the properties of a heap after adding a new element.
void heapify(int *heap, int n, int i)
{
   int l = 2*i + 1;
   int h = 2*i + 2;
   int j = i;
   if(l < n && heap[i] < heap[l])
   {
       i = l;
   }
   if(h < n && heap[i] < heap[h])
   {
       i = h;
   }
   if(i != j)
   {
       int temp = heap[i];
       heap[i] = heap[j];
       heap[j] = temp;
       heapify(heap, n, i);
   }
}

// Building max Heap using maxHeap function.
void maxHeap(int *heap, int n)
{
   for(int i = (n-1)/2; i >= 0; i--)
   {
       heapify(heap, n, i);
   }
}

// This function will generate new 100 elements and add them to the heap.
// Whenever needed, it doubles the heap size.
int *grow(int *heap, int *n, int *el)
{
   // Condition checks if heap can add 100 new elements with current size, if not than double the current heap size.
   if(*el + 100 > *n)
   {
       printf("\nCurretn size of heap: %d\n", *n);
       int x = (*n);
       *n = (2*x);
       int *arr = new int[2*x];
       for(int i = 0; i < x; i++)
       {
           arr[i] = heap[i];
       }
       heap = arr;
       printf("Size of heap after doubling: %d\n\n", *n);
   }

   // Generating 100 new elements and addign them into heap.
   int x = *el;
   for(int i = x; i < (x+100); i++)
   {
       int y = rand();
       heap[i] = (y%2000 + 1);
       cout << heap[i] << " ";
       if((i+1)%20 == 0)
       {
           cout << '\n';
       }
   }
   *el += 100;
   maxHeap(heap, *el);
   return heap;
}

// printing the heap elements int increasing order.
void print(int *heap, int n)
{
   cout << "\n Heap Elements :\n";
   int h = n-1;
   maxHeap(heap, n);
   while(h >= 0)
   {
       int temp = heap[0];
       heap[0] = heap[h];
       heap[h] = temp;
       heapify(heap, h, 0);
       h--;
   }
   for(int i = 0; i < n; i++)
   {
       cout << heap[i] << " ";
   }
   cout << '\n';
}

// Main function.
int main(void)
{
   int *heap = new int[100];
   int n = 100;
   int elements = 0;
   bool cond = false;
   char ch, x;
   cout << "Want to generate 100 Elements (Y/N) : \n";
   cin >> ch;
   if(ch == 'Y' || ch == 'y')
   {
       cond = true;
   }
   while(cond)
   {
       heap = grow(heap, &n, &elements);
       cout << "Want to generate next 100 elements (Y/N) : " << '\n';
       cin >> ch;
       if(ch == 'N' || ch == 'n')
       {
           cond = false;
       }
   }
   print(heap, elements);
   return 0;
}

Screenshot of output:-

Want to generate 100 Elements (Y/N) : 1384 887 778 916 1794 336 1387 493 650 1422 363 28 691 60 1764 1927 541 1427 1173 1737 1212 1369 568 430 1783 1531 863 1124 68 1136 1930 1803 23 1059 1070 168 1394 457 1012 43 230 1374 422 920 1785 538 1199 325 316 371 414 1527 92 981 1957 1874 863 1171 997 1282 306 926 1085 328 337 506 847 1730 1314 1858 125 1896 1583 546 815 1368 1435 365 44 1751 1088 809 1277 1179 1789 1585 1404 652 755 400 1933 1061 1677 1369 1740 13 227 587 95 1540 Want to generate next 100 elements (Y/N) : Curretn size of heap: 100 Size of heap after doubling: 200 796 571 1435 379 1468 602 98 903 1318 493 653 757 1302 281 287 1442 1866 1690 445 620 441 730 32 118 98 1772 482 676 710 928 568 1857 1498 354 587 966 1307 684 220 625 1529 872 1733 830 1504 20 271 1369 1709 716 341 150 1797 724 619 246 847 1452 922 1556 380 1489 1765 229 1842 351 1194 1501 1035 1765 125 915 988 1857 1744 492 228 366 1860 1937 1433 552 438 1229 1276 1408 1475 122 859 396 30 1238 236 1794 1819 429 144 1012 1929 1530 Want to generate next 100 elements (Y/N) : Curretn size of heap: 200 Size of heap after doubling: 400 777 405 444 1764 614 539 607 841 905 819 1129 689 1370 1918 1918 997 1325 1744 1471 184, 491 1500 1773 726 1645 1591 1506 140 955 1787 1670 83 543 465 198 1508 1356 805 349 612 1623 1829 1300 1344 1747 1569 341 1423 1312 1811 1606 1802 1662 1731 879 1306 1321 737 1445 627 523 1466 709 1417 283 1259 925 1638 63 1625 601 37 1453 1900 1380 1551 1469 72 974 1132, 1882 931 934 1895 661 164 1200 1982 900 997_960 1774 814 1669 1191 1096 927 467 1085 1341 Want to generate next 100 elements (Y/N) : Heap Elements : 13 20 23 28 30 32 37 43 44 60 63 68 72 83 92 95 98 98 118 122 125 125 140 144 150 164 168 184 198 220 227 228 229 230 236 246 271 281 283 287 306 316 325 328 336 337 341 341 349 351 354 363 365 366 371 379 380 396 400 405 414 422 429 430 438 441 444 445 457 465 467 482 491 492 493 49 3 506 523 538 539 541 543 546 552 568 568 571 587 587 601 602 607 612 614 619 620 625 627 650 652 653 661 676 684 689 691 709 710 716 724 726 730 737 755 757 777 778 796 805 809 814 815 819 830 841 847 847 859 863 863 872 879 887 900 903 905 915 916 920 922 925 926 927 928 931 934 95 5 960 966 974 981 988 997 997 997 1012 1012 1035 1059 1061 1070 1085 1085 1088 1096 1124 1129 1132 1136 1171 1173 1179 1191 1194 1199 1200 121

306 926 1085 328 337 506 847 1730 1314 1858 125 1896 1583 546 815 1368 1435 365 44 1751 1088 809 1277 1179 1789 1585 1404 652 755 400 1933 1061 1677 1369 1740 13 227 587 95 1540 Want to generate next 100 elements (Y/N) : Curretn size of heap: 100 Size of heap after doubling: 200 796 571 1435 379 1468 602 98 903 1318 493 653 757 1302 281 287 1442 1866 1690 445 620 441 730 32 118 98 1772 482 676 710 928 568 1857 1498 354 587 966 1307 684 220 625 1529 872 1733 830 1504 20 271 1369 1709 716 341 150 1797 724 619 246 847 1452 922 1556 380 1489 1765 229 1842 351 1194 1501 1035 1765 125 915 988 1857 1744 492 228 366 1860 1937 1433 552 438 1229 1276 1408 1475 122 859 396 30 1238 236 1794 1819 429 144 1012 1929 1530 Want to generate next 100 elements (Y/N) : Curretn size of heap: 200 Size of heap after doubling: 400 777 405 444 1764 614 539 607 841 905 819 1129 689 1370 1918 1918 997 1325 1744 1471 184 491 1500 1773 726 1645 1591 1506 140 955 1787 1670 83 543 465 198 1508 1356 805 349 612 1623 1829 1300 1344 1747 1569 341 1423 1312 1811 1606 1802 1662 1731 879 1306 1321 737 1445 627 523 1466 709 1417 283 1259 925 1638 63 1625 601 37 1453 1900 1380 1551 1469 72 974 1132 1882 931 934 1895 661 164 1200 1982 900 997 960 1774 814 1669 1191 1096 927 467 1085 1341 Want to generate next 100 elements (Y/N) : Heap Elements : 13 20 23 28 30 32 37 43 44 60 63 68 72 83 92 95 98 98 118 122 125 125 140 144 150 164 168 184 198 220 227 228 229 230 236 246 271 281 283 287 306 316 325 328 336 337 341 341 349 351 354 363 365 366 371 379 380 396 400 405 414 422 429 430 438 441 444 445 457 465 467 482 491 492 493 49 3 506 523 538 539 541 543 546 552 568 568 571 587 587 601 602 607 612 614 619 620 625 627 650 652 653 661 676 684 689 691 709 710 716 724 726 730 737 755 757 777 778 796 805 809 814 815 819 830 841 847 847 859 863 863 872 879 887 900 903 905 915 916 920 922 925 926 927 928 931 934 95 5 960 966 974 981 988 997 997 997 1012 1012 1035 1059 1061 1070 1085 1085 1088 1096 1124 1129 1132 1136 1171 1173 1179 1191 1194 1199 1200 121 2 1229 1238 1259 1276 1277 1282 1300 1302 1306 1307 1312 1314 1318 1321 1325 1341 1344 1356 1368 1369 1369 1369 1370 1374 1380 1384 1387 1394 1404 1408 1417 1422 1423 1427 1433 1435 1435 1442 1445 1452 1453 1466 1468 1469 1471 1475 1489 1498 1500 1501 1504 1506 1508 1527 1529 1530 15 31 1540 1551 1556 1569 1583 1585 1591 1606 1623 1625 1638 1645 1662 1669 1670 1677 1690 1709 1730 1731 1733 1737 1740 1744 1744 1747 1751 1764 1764 1765 1765 1772 1773 1774 1783 1785 1787 1789 1794 1794 1797 1802 1803 1811 1819 1829 1842 1857 1857 1858 1860 1866 1874 1882 1895 1896 1 900 1918 1918 1927 1929 1930 1933 1937 1957 1982