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.

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

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.

Question