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.

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 2 years ago

1.Instead of Build-Max-Heap, we could use Heap-Insert-Max to build a tree with heap property. Write a...

1.Instead of Build-Max-Heap, we could use Heap-Insert-Max to build a tree with heap property. Write a pseudocode for that procedure, also evaluate it’s time complexity. 2. How Insertion sort works on the following array [16, 12, 3, 27, 9, 4, 5, 7]]

Java Question 5: Count elements in the heap Write a function that returns the number of...

Java Question 5: Count elements in the heap Write a function that returns the number of elements in a min heap strictly less than a given number. Method signature: public static int elemNumHeap(PriorityQueue minHeap, int val) Please also include testers.

Assume there is a 30-byte heap. The free list for this heap has two elements on...

Assume there is a 30-byte heap. The free list for this heap has two elements on it. One entry describes the first 10-byte free segment (bytes 0-9), and one entry describes the other free segment (bytes 20-29). Now assume we have a request for just a single byte of memory. In this case, the allocator will perform an action known as __________ to find a free chunk of memory that can satisfy the request. splitting coalescing chopping relocating Refer to...

We learned that when calling subprograms or functions that we can pass data to the subprogram...

We learned that when calling subprograms or functions that we can pass data to the subprogram or function by ‘value’ or by ‘reference’. Describe what each approach is, how it works and what the potential security disadvantage is when passing parameters by reference.

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...

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

Can you please explain loop invariant for Heapsort, in which Min-Heapify and Build-Min-Heap are correct

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...

Question