Question

In: Computer Science

Please fill in the 20 blanks below: 1, Considering using sorted and unsorted array as priority...

  1. Please fill in the 20 blanks below:

1, Considering using sorted and unsorted array as priority queue to do sorting. For an input array, we insert each element to a PQ and remove them out to an output array. Please write the arrays below:

Input array: 2,7,5,3

  1. Sorted PQ after 1st Insertion:
  2. Sorted PQ after 2nd Insertion:
  3. Sorted PQ after 3rd Insertion:
  4. Sorted PQ after 4th Insertion:
  5. Output array after 1st removeMin:
  6. Output array after 2nd removeMin:
  7. Output array after 3rd removeMin:
  8. Output array after 4th removeMin:

Input array: 2,7,5,3

  1. Unsorted PQ after 1st Insertion:
  2. Unsorted PQ after 2nd Insertion:
  3. Unsorted PQ after 3rd Insertion:
  4. Unsorted PQ after 4th Insertion:
  5. Output array after 1st removeMin:
  6. Output array after 2nd removeMin:
  7. Output array after 3rd removeMin:
  8. Output array after 4th removeMin:

2, If I use upheap strategy to construct a heap(array as implementation) from above array, what is the array of the heap of each step?

  1. Step 1:
  2. Step 2:
  3. Step 3:
  4. Step 4:

Solutions

Expert Solution

The various instances of the array , after the various operations as required by question is presented below:

Q1)

Input array: 2,7,5,3

1. Sorted PQ after 1st Insertion: [2]

2. Sorted PQ after 2nd Insertion: [2,7]

3. Sorted PQ after 3rd Insertion: [2,5,7]

4. Sorted PQ after 4th Insertion: [2,3,5,7]

5. Output array after 1st removeMin: [3,5,7]

6. Output array after 2nd removeMin: [5,7]

7. Output array after 3rd removeMin:[7]

8. Output array after 4th removeMin:[ ]

Input array: 2,7,5,3

1. Unsorted PQ after 1st Insertion: [2]

2. Unsorted PQ after 2nd Insertion: [2,7]

3. Unsorted PQ after 3rd Insertion: [2,7,5]

4. Unsorted PQ after 4th Insertion: [2,7,5,3]

5. Output array after 1st removeMin: [7,5,3]

6. Output array after 2nd removeMin: [7,5]

7. Output array after 3rd removeMin: [7]

8. Output array after 4th removeMin: [ ]

Q2)

1. Step 1: [2]

2. Step 2: [7,2]

3. Step 3: [7, 2, 5]

4. Step 4: [7,3,5,2]

venereology answered 1 month ago
Next > < Previous

Related Solutions

C++ Program 1–Implement a Priority Queue(PQ) using an UNSORTED LIST. Use an array size of 10...
C++ Program 1–Implement a Priority Queue(PQ) using an UNSORTED LIST. Use an array size of 10 elements. Use a circular array: Next index after last index is 0. Add the new node to next available index in the array. When you add an element, add 1 to index (hit max index, go to index 0). Test if array in full before you add. When you remove an element, from the list, move the following elements to the left to fill...
Create an array of 10,000 elements, use sorted, near sorted, and unsorted arrays. Implement find the...
Create an array of 10,000 elements, use sorted, near sorted, and unsorted arrays. Implement find the kth smallest item in an array. Use the first item as the pivot. Compare sets of results using a static call counter. Reset counter before running another search. Create a Test drive to exhaustively test the program. // Assume all values in S are unique. kSmall(int [] S, int k): int (value of k-smallest element) pivot = arbitrary element from S:  let’s use the first...
Implement a Priority Queue (PQ) using an UNSORTED LIST. Use an array size of 10 elements....
Implement a Priority Queue (PQ) using an UNSORTED LIST. Use an array size of 10 elements. Use a circular array: Next index after last index is 0. Add the new node to next available index in the array. When you add an element, add 1 to index (hit max index, go to index 0). Test if array in full before you add. When you remove an element, from the list, move the following elements to the left to fill in...
C++ Fill in the blanks please You are required to fill in the blanks in this...
C++ Fill in the blanks please You are required to fill in the blanks in this program. Consider that: -In main, the variables price and quantity were given the names of p (double) and q (int), respectively. -In the getData function, the parameters associated with the main variables p and q were called pp and pq, respectively. // Prototype: Do not include the names // of the variables in the prototype void getData (FILLTHEBLANK , FILLTHEBLANK); int main () {...
using Linux please fill in the blanks : telnos files:
  using Linux please fill in the blanks : telnos files: telnos telnos2 Hale Elizabeth Bot   744-6892Harris Thomas Stat 744-7623Davis Paulette Phys 744-9579Cross Joseph   MS    744-0320Holland Tod    A&S   744-8368 Hale Elizabeth Bot   744-6892Harris Thomas Stat 744-7623Davis Paulette Phys 744-9579Holland Tod    A&S   744-8368 telnos3 telnos 4 Hale Elizabeth Bot   744-6892Harris Thomas Stat 744-7623Smith John     Comsc 744-4444Davis Paulette Phys 744-9579Cross Joseph   MS    744-0320Holland Tod    A&S   744-8368 Hale Elizabeth Bot   744-6892Smith John     Comsc 744-4444Davis Paulette Phys 744-9579Cross Joseph   MS    744-0320Holland Tod    A&S   744-8368...
please fill in the blanks using c program or lunix with the answers being highlighted 1....
please fill in the blanks using c program or lunix with the answers being highlighted 1. You will now need four files. These are telnos, telnos2, telnos3, telnos4. These files are all short files that contain names, departments, and telephone numbers. This is what they look like. telnos telnos2 Hale Elizabeth Bot   744-6892 Harris Thomas Stat 744-7623 Davis Paulette Phys 744-9579 Cross Joseph   MS    744-0320 Holland Tod    A&S   744-8368 Hale Elizabeth Bot   744-6892 Harris Thomas Stat 744-7623 Davis Paulette Phys...
Fill in the blanks in the MATLAB code below.
Fill in the blanks in the MATLAB code below. (Do not type unnecessary words or blank spaces in your response. The correct answers are case-sensitive.) % Consider a row vector v. % Complete the lines of code below to find the average and standard deviation of the elements of vector v such that these two values are assigned to variables M and S, respectively. E = G =
Given the following program with fill in the blanks, implement the PQ class which is priority...
Given the following program with fill in the blanks, implement the PQ class which is priority Queue MAX heap; the higher the number, the higher the prority of that number. None of the public methods has been implemented. You will need to write other methods to help implement some of the methods. For example you will need to implement bubbleUp to help with the insert method. Methods to implement: insert -> insert one element into the PQ and maintain heap...
using lunix or C programming to answer this lab please fill in the blanks with the...
using lunix or C programming to answer this lab please fill in the blanks with the answere being highlighted, so i can understand. First, type the following command:             sort employee What is the order that employee is sorted in? ___________________________________________ Give a brief description of how the file is sorted. _____________________________________________________________________________________________________________________________________________________________________________________________________ Now, sort on the field for last name.         sort +1 employee Look at the sorted file. Are all the names sorted in alphabetical order? ______________________ Give a brief description...
Use the mechanism below to fill in the blanks in the statements. Step 1 A +...
Use the mechanism below to fill in the blanks in the statements. Step 1 A + B → C Step 2 C + D → B + E Substance is a catalyst in this mechanism Substance is an intermediate in this mechanism
ADVERTISEMENT
Subjects
ADVERTISEMENT
Latest Questions
ADVERTISEMENT