1answer.
Ask question
Login Signup
Ask question
All categories
  • English
  • Mathematics
  • Social Studies
  • Business
  • History
  • Health
  • Geography
  • Biology
  • Physics
  • Chemistry
  • Computers and Technology
  • Arts
  • World Languages
  • Spanish
  • French
  • German
  • Advanced Placement (AP)
  • SAT
  • Medicine
  • Law
  • Engineering
barxatty [35]
3 years ago
11

Indicate the time efficiency classes of the three main operations (i.e., FindMax, DeleteMax, and Insert) of the priority queue i

mplemented as: 1. an unsorted array 2. a sorted array 3. a binary search tree 4. an AVL tree 5. a heap
Computers and Technology
1 answer:
Sholpan [36]3 years ago
5 0

Answer:

Appropriate explanation to the questions below.

Explanation:

<u>Using an Unsorted Array </u>

An unsorted array will take more time to find data hence, findMax will be slow. Time complexity is O(N). Also if we keep the array unsorted, then insert is O(1) -- ignoring the time to expand the array, but deleteMax is O(N) since we must search the whole array for the largest value.

The empty operation is trivial -- just return true if numItems == 0, so it (and the constructor) are both O(1).

<u>Using an Sorted Array </u>

The findMax operation will be faster as compared to unsorted array as either the array is sorted in descending or in ascending order the time complexity will be O(1). Also if we use an array to store the values in the priority queue, we can either store the values in sorted order (which will make the insert operation slow, and the deleteMax operation fast), or in arbitrary order (which will make the insert operation fast, and the deleteMax operation slow). Note also that we'll need a field to keep track of the number of values currently in the queue, we'll need to decide how big to make the array initially, and we'll need to expand the array if it gets full. Here's a partial class definition:

public class PriorityQueue {    

   private Comparable[] queue;

   private int numItems;

   private static final int INIT_SIZE = 10;    

   public PriorityQueue() {

       queue = new Comparable[INIT_SIZE];

numItems = 0;

   }

}

As mentioned above, if we keep the array sorted, then the insert operation is worst-case O(N) when there are N items in the queue: we can find the place for the new value efficiently using binary search, but then we'll need to move all the larger values over to the right to make room for the new value. As long as we keep the array sorted from low to high, the deleteMax is O(1) -- just decrement numItems and return the last value.

<u>Using a BST </u>

If we use a BST, then the largest value can be found in time proportional to the height of the tree by going right until we reach a node with no right child. Removing that node is also O(tree height), as is inserting a new value. If the tree stays balanced, then these operations are no worse than O(log N); however, if the tree is not balanced, insert and deleteMax can be O(N). As for the linked-list implementation, there is no need for a numItems field.

BST = In avg case it will take o(logn) worst case 0(n)

Using an AVL Tree

AVL Tree:  

  Insertion/deletion/searching: O(log n) in all cases.

But Complexity isn't everything, there are other considerations for actual performance.

For most purposes, most people don't even use an AVL tree as a balanced tree (Red-Black trees are more common as far as I've seen), let alone as a priority queue.

This is not to say that AVL trees are useless, I quite like them. But they do have a relatively expensive insert. What AVL trees are good for (beating even Red-Black trees) is doing lots and lots of lookups without modification. This is not what you need for a priority queue.

<u> </u>

<u>Using a Heap </u>

When a priority queue is implemented using a heap, the worst-case times for both insert and deleteMax are logarithmic in the number of values in the priority queue.

For the insert operation, we start by adding a value to the end of the array (constant time, assuming the array doesn't have to be expanded); then we swap values up the tree until the order property has been restored. In the worst case, we follow a path all the way from a leaf to the root (i.e., the work we do is proportional to the height of the tree). Because a heap is a balanced binary tree, the height of the tree is O(log N), where N is the number of values stored in the tree.

The deleteMax operation is similar: in the worst case, we follow a path down the tree from the root to a leaf. Again, the worst-case time is O(log N).

You might be interested in
He has a new Wi-Fi router that connects wirelessly to a new desktop and two new laptops, in addition to multiple smartphones, ta
arsen [322]

Answer: LAN(Local area network)

Explanation:

Local area network(LAN) is the network that is made to cover small amount for area for providing network and computer services.It can usually span in the areas such as a personal room, single building etc.

  • It connects different peripheral devices like printer, switches, tabs etc with the computing system in small certain areas.
  • According to the question, the individual should use LAN network for linking computer with the printer device.
  • As the person has connected laptops, tablets,smartphones, network of printer etc within a network in single space, he is interacting these devices using local area network.
6 0
2 years ago
You have just taken over management of a server on which the previous server administrator has set up several server components,
Arisa [49]

Answer:

d. Ensure file caching and flushing are enabled for all disk drives.

Explanation:

When the disk reading and writing is delayed and the server performance is also slow after taking over management of a server.Previously the server has several server components.So to increase the performance we should ensure caching of the file and make sure that the flushing is enabled for all disk drives.Hence the answer to this question is option d.

8 0
2 years ago
You can customize backdrops in Scratch, adding text or freestyle drawings over the initial image
sveticcg [70]

Answer:

A. True

Explanation:

ive done this myself

https://scratch.mit.edu/projects/395142260/

3 0
2 years ago
You are to design class called Employee whose members are as given below:
frozen [14]

Answer:

//The Employee Class

public class Employee {

   char name;

   long  ID;

//The constructor  

public Employee(char name, long ID) {

       this.name = name;

       this.ID = ID;

   }

//Method Get Person

   public void getPerson (char newName, long newId){

       this.ID = newName;

       this.ID = newId;

   }

//Method Print

   public void print(){

       System.out.println("The class attributes are: EmpName "+name+" EmpId "+ID);

   }

}

The working of the class is shown below in another class EmployeeTest

Explanation:

public class EmployeeTest {

   public static void main(String[] args) {

       Employee employee1 = new Employee('a', 121);

       Employee employee2 = new Employee('b', 122);

       Employee employee3 = new Employee('c', 123);

       employee1.print();

       employee2.print();

       employee3.print();

   }

}

In the EmployeeTest class, Three objects of the Employee class are created.

The method print() is then called on each instance of the class.

6 0
3 years ago
Print 'userNum1 is negative" if userNum1 is less than 0. End with newline Convert userNum2 to 0 if userNum2 is greater than 9. O
dlinn [17]

Answer:

#include <stdio.h>

int main()

{

   int userNum1;

   int userNum2;

   

   userNum1 = -1;

   userNum2 = 7;

   

   if (userNum1 < 0)

       printf("userNum1 is negative. \n");

       

   if(userNum2 > 9)

       userNum2 = 0;

   else

       printf("userNum2 is less than or equal to 9.\n");

   return 0;

}

Explanation:  

Initialize userNum1 and userNum2.

If userNum1 is less than 0, print 'userNum1 is negative" and end with newline.

if userNum2 is greater than 9, assign 0 to userNum2.

Otherwise, print "userNum2 is less than or equal to 9 and end with newline.

8 0
3 years ago
Other questions:
  • Which question best addresses the issue of risk with a new job?
    7·2 answers
  • (Complete the Problem-Solving discussion in Word for Programming Challenge 2 on page 404. Your Problem-Solving discussion should
    13·1 answer
  • What is structured​ knowledge?
    10·1 answer
  • Hurry answerrrrrrr pleaseee
    11·2 answers
  • Microsoft's ____ is one of the major web-based development environments.
    12·1 answer
  • Someone gave me flashcards on a keychan. I have to memorize them and then give them back. Can I back them up to my PC by creatin
    5·1 answer
  • What is HTML? (list down any 5 points)
    12·1 answer
  • In the early 1800's, a “computer" was not a machine, it was a person who did math
    8·2 answers
  • Imagine that a team of scientists test a certain hypothesis, and the experimental results show that it is false.
    6·1 answer
  • Which of the following items in the folder window allows users to view locations which have been visited before?
    6·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!