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
Again, consider what you believe to be the goal of performing a penetration test. Why would you worry about doing any privilege
Strike441 [17]

Answer:

Penetration monitoring is conducted based on the vulnerability evaluation (Were a susceptibility evaluated and mentioned).

Explanation:

Penetration Test

  • Penetration testing is carried out from both within (the network or application) as well as outside that aims to gain access to the system to evaluate if any suspicious activity or improper behavior is likely within the device.
  • When there are some other potential security vulnerabilities, they are all found in the integration check that involves vulnerability assessment for frameworks and checking for network management.
  • Automation of penetration testing is used to make it work better.
  • Penetration monitoring deals with the same risk evaluation correlated with a disadvantage.

Privilege escalation

  • They need to think about known vulnerabilities as the system for network management works conditional on the privilege rates. Such that, increasing user has an article has highlighted and the consumer is only allowed to control or use the resources that should be used appropriately, depending on the level of privilege.
  • If he gets elevated access then it will be a failure to have access control mechanism.

Leaving backdoors

  • The creator uses backdoors to test the system's functionality during the designing processes.
  • The loophole can be a workaround overriding the identification for all users, or a default password.
  • They would need to worry about leaving the backdoor because the backdoor.which is performed either deliberately or involuntarily will circumvent the entire security mechanism.
  • During the intrusion testing process, the both privilege increase and the escape from the gateway can be discovered due to the research being done both inside and outside the device.
  • The tester's testing phase acts as various users so that any destabilization of access may be found.
  • The tester will use all numerous methods to supersede the technique of official approval, but when there are certain backdoors, maybe he can start by pointing that out.

6 0
3 years ago
Cursor/Blinking line is used to show current_ on document. A- Color b- Status c- Type d- Location
Natalija [7]

Answer:

d. Location

Pretty sure this is it.

7 0
2 years ago
A collection of realated files is called a
Thepotemich [5.8K]

The answer to this question would be:

database/records

They all have in common the same files.

4 0
3 years ago
Which three pieces of information should be included in an artist statement? Select all that apply.
Dima020 [189]

Answer:

There is no answers given??

Explanation:

N/A

4 0
2 years ago
Without using any additional variables, and without changing the values of ndays or the elements of the parkingTickets array, wr
dusya [7]

Answer:

Explanation:

mostTickets=0;

for (k=0; k< ndays; k++){

if (parkingTickets[k]>mostTickets) mostTickets=parkingTickets[k];

}

7 0
3 years ago
Other questions:
  • A(n) _____ can be used to convert digitized documents into ascii (american standard code for information interchange) text that
    6·1 answer
  • With arbitrary code execution, the ________________ launches ("spawns") a command shell from which instructions can then be issu
    11·1 answer
  • A database administrator (DBA) must have a clear understanding of the fundamental business of an organization, be proficient in
    11·1 answer
  • Write a program to convert a fraction to a decimal. Have your program ask for the numerator first, then the denominator. Make su
    10·1 answer
  • What font family is Times New Roman an what font family is Arial?
    9·2 answers
  • Why do you usually find domain names instead of IP addresses in a URL? Select one: a. An IP address would make your web page loa
    11·1 answer
  • Which 1947 Invention paved the way for the Digital Revolution?
    12·2 answers
  • Office 365 ProPlus can be deployed to your enterprise. When doing so, which tool enables you to choose the language, hardware ar
    5·1 answer
  • Which two features offered by SharePoint
    12·1 answer
  • The area that we can see just after windows is started is subject​
    6·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!