We can build a heap by repeatedly calling the insert function to insert the elements into...

We can build a heap by repeatedly calling the insert function to insert the elements into the heap. Here is pseudocode:

buildHeap(A)

h = new empty heap

for each element e in A

h.insert(e)

What is the Big-O runtime of this version of buildHeap? Justify your answer.

Solutions

Expert Solution

Heap insertion is followed by heapify in order to maintain the heap property after insertion. Heapify function take order of height, O(h) time to update the heap.

Attached here is the derivation, as to how buildheap has O(n) time complexity. Please refer to stardard book or some website to know how the series expansion used in last step evaluates to 2.

venereology answered 1 year ago

Next > < Previous

Related Solutions

Consider a binomial heap where only insert and findmin operations are allowed (no extractmin). Show that...

Consider a binomial heap where only insert and findmin operations are allowed (no extractmin). Show that both of these operations can be done in amortized O(1) time. Hint: For findmin consider explicitely storing a pointer to the tree with minimum root and then update it during insert if needed. For insert, you’ll need to use amortization and develop a good potential function.

Where in a max heap with over 15 elements can you find the third-largest value? Select...

Where in a max heap with over 15 elements can you find the third-largest value? Select all that apply. a child of the right child of the root, a child of the left child of the root, leaf node, left or right child of the root, root

C Programming build a function that is outside of main domain but can be called Build...

C Programming build a function that is outside of main domain but can be called Build a function that will : - Take 3 arrays and their lengths as input: Array 1 for even numbers, Array 2 for odd numbers. Both 1 and 2 have the same size - put all elements in array 3 elements from array 1 should be placed in the even indexes and elements of array 2 should be placed in the odd indexes, in increasing...

Recall that an array could be a convenient way of storing the elements of a Heap....

Recall that an array could be a convenient way of storing the elements of a Heap. Give a Pseudocode that determines whether an array H[1..N] is indeed a Heap, i.e., it’s elements satisfy the Heap property.

In this assignment, we will build custom functions in R. As an example, the following function...

In this assignment, we will build custom functions in R. As an example, the following function called addPercent converts a value into a percentage with one decimal place. addPercent - function(x){ percent - round(x*100, digits = 1) result - paste(percent, "%", sep = "") return(result) } Below are a few output results from this function. addPercent(.1) [1] "10%" addPercent(10) [1] "1000%" addPercent(10.1) [1] "1010%" addPercent(0.1443) [1] "14.4%" Write a custom R function that inputs a temperature in Fahrenheit Fo and...

Part 1: Getting started and calling a function from a function. In this part, you will...

Part 1: Getting started and calling a function from a function. In this part, you will work with functions and functions that call functions. All code will be in main.cpp. Testing and grading will be via zyLab. Start with the template in zyBook. Write the following function: FindMax4(double num1, double num1, double num3, double num4) that returns the max of the arguments. Implement FindMax4() such that the body of the function comprises only a return statement that invokes FindMax() multiple...

Write a program to insert the following elements into a hash table of size 17. The...

Write a program to insert the following elements into a hash table of size 17. The hash function is X mod 17 where X is the input element. 6, 12, 34, 29, 28, 11, 23, 7, 0, 33, 30, 45 Use linear probing to resolve any collisions.

Problem 5: Find Smallest Elements In this problem, we will write a function to find the...

Problem 5: Find Smallest Elements In this problem, we will write a function to find the smallest elements of a list. Define a function named find_smallest() that accepts two parameters: x and n. The parameter x is expected to be a list of values of the same time, and n is expected to be an either integer, or the value None, and should have a default value of None. • If n is set to None, then the function should...

This function will receive a list of elements with duplicate elements, this function should remove the...

This function will receive a list of elements with duplicate elements, this function should remove the duplicate elements in the list and return a list without duplicate elements. The elements in the returned list must be in the same order that they were found in the list the function received. A duplicate element is an element found more than one time in the specified list. JAVA

Build a Max Heap using the following: A= {20, 15, 10, 14, 8, 6, 9}

Subjects