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
(tco 8) when a file is opened in the append mode, the file pointer is positioned
Artyom0805 [142]
At the end of the file, so that additional data is appended while the existing data stays intact.
6 0
3 years ago
EASY AND I GIVE BRAINLIEST!!! What is a good jeopardy question about operating systems?
madam [21]

 ______ is used in operating system to separate mechanism from policy
<span><span>A. Single level implementation</span><span>B. Two level implementation</span><span>C. Multi level implementation</span><span>D. None</span></span>
3 0
3 years ago
1. Grouping Data in a Pivot Table can help you do what?
valentina_108 [34]

Answer:

1.Grouping data in a PivotTable can help you show a subset of data to analyze. For example, you may want to group an unwieldy list of dates or times (date and time fields in the PivotTable) into quarters and months, like this image. Note:  The time grouping feature is new in Excel 2016.

2.Select the rows or columns you wish to grouP

On the Data tab, in the Outline group, click the Group command.  

In the Group dialog box, select Rows or Columns and click OK.

3.Select the rows or columns you wish to ungroup.

On the Data tab, in the Outline group, click the Ungroup command.  

In the Group dialog box, select Rows or Columns and click OK.

4.

1.Launch Microsoft Excel.

2

Browse to and open the workbook file containing the pivot table and source data for which you need filter data.

3

Select the worksheet containing the pivot tab and make it active by clicking the appropriate tab.

4

Determine the attribute by which you want to filter data in your pivot table.  

The attribute should be one of the column labels from the source data that is populating your pivot table.

For example, assume your source data contains sales by product, month and region. You could choose any one of these attributes for your filter and have your pivot table display data for only certain products, certain months or certain regions. Changing the filter field would determine which values for that attribute are shown.

5

Force the Pivot Table Wizard or Field List to launch by clicking a cell inside the pivot table.

6

Drag and drop the column label field name you wish to apply as a filter to the "Report Filter" section of the pivot table field list.  

This field name may already be in the "Column Labels" or "Row Labels" section.

It may be in the list of all field names as an unused field.

7

Set the filter to display one of the values for the field.  

You can set the filter to display all values or only one. Click the arrow beside the filtered label and check the "Select Multiple Items" check box if you would like to select certain values for your filter.

Explanation:

PLZ MARK ME AS A BRAINLIST ;)

4 0
3 years ago
Thabo has a small barber shop and he uses Microsoft applications to keep track of his stock and to create posters for advertisin
kirza4 [7]

An information system is crucial to the success of a business. Itemized below are five benefits of operating an information system in a business.

<h3>What are the benefits of an Information System?</h3>

Information systems are important because:

  1. They help to increase and enhance operational efficiencies such as accounting, sales, inventory, and HR operations.
  2. They help to minimize costs. As the business makes more and more informed decisions, its costs will drop.
  3. It enhances customer service. Information about customers helps the business to tailor its services to the requirements of each customer.
  4. Information system helps the decision-makers in the business to make better and more informed decisions.
  5. Information systems help to ensure business continuity.

<h3>What are the requirements for creating an information system?
</h3>

An information system requires the following:

  • Hardware for the computer workstation and addendums
  • Software
  • A network communication amongst the computers and hardware
  • a map of the company's processes and the people responsible for such processes
  • A procedural manual.
  • Existing data from the business.

For the barber's shop, for example, some of the components of the information system he must put in place are:

A workstation that collects information about:

  • Clients
  • Details of Sales
  • Expenses
  • Compliance dates and records etc.

Learn more about Information Systems at:

brainly.com/question/25226643

4 0
2 years ago
Which browser do most web users use and why do you think that it is that way? Make sure you search online for statistics to conf
oksian1 [2.3K]

Answer:

2b2t

Explanation:

2b2t

4 0
3 years ago
Other questions:
  • A(n) _____________ is a simple tool that can help identify computers/devices or communication circuits that have higher-than-ave
    14·1 answer
  • Over time, programming languages have evolved in phases called ________.
    5·2 answers
  • In a system using the fixed partitions memory allocation scheme, given the following situation (and using a decimal form): After
    9·1 answer
  • What is also known as a visual aid in presentation
    15·1 answer
  • All systems have ___________.
    9·2 answers
  • ________type of website is an interactive website kept constantly updated and relevant to the needs of its customers using a dat
    5·1 answer
  • Waygate's residential Internet modem works well but is sensitive to power-line fluctuations. On average, this product hangs up a
    6·1 answer
  • What would be a social networking page background for Sigmund Freud?
    15·1 answer
  • Help me. thank you very much
    14·1 answer
  • Profitability, consumer relations, and competition are involved in what kinds of concerns in the design process?
    12·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!