Show that the worst-case time complexity of the heap

Assignment Help Computer Engineering

Reference no: EM132158997

Use the statement counting approach to show that the worst-case time complexity of the heap inser- tion and deletion algorithms given are O(log n).

Algoirthm insert(H, e)
Inserts the element e into the heap H.

Insert e into H normally , as in ArrayedBinaryTreeWithCursors280 <I>

// (put it in the left-most open position at the bottom level of the tree)

while e is larger than its parent and is not at the root: swap e with its parent

Algorithm deleteItem(H)
Removes the largest element from the heap H.

// Since the largest element in a heap is always at the root...

Remove the root from H normally , as in ArrayedBinaryTreeWithCursors280 <I>

// (copy the right-most element in the bottom level, e, into the root, // remove the original copy of e.)

while e is smaller than its largest child swap e with its largest child

Reference no: EM132158997

Questions Cloud

Which arithmetic operator gives you the remainder : A number that is evenly divisible by 2 is even. An odd number has a remainder of 1 when divided by 2. Which arithmetic operator gives you the remainder?

Probability an individual large-cap domestic stock fund : What is the probability an individual large-cap domestic stock fund had a three-year return of at least 10%?

Write skeletal code for the classes and methods : Write skeletal code for the classes and methods to describe swim, grow, and change in frog's behaviour.

Display the sum of the negative values : Use a single while-loop to display the decimal values -2.3 to 2.9 (inclusive), incrementing by 0.4 for each value displayed.

Show that the worst-case time complexity of the heap : Use the statement counting approach to show that the worst-case time complexity of the heap inser- tion and deletion algorithms given are O(log n).

Independently of the outcomes of the other games : The Cubs and Blue Jays play in the World Series where the first team to win 4 games is declared the overall winner.

National association of colleges and employers : According to the National Association of Colleges and Employers, finance graduates make an average of (µ) $52,402 a year.

When do we worry about the possibility of committing : A research analyst believes that average back-to-school spending is more than a trade group's prediction of $500. Specify the null and alternative hypothesis.

What is the test statistic for sample of size 26 : What is the test statistic for sample of size 26, mean 14.90, and standard deviation 1.20? Enter the test statistic with 2 decimal places.

User Account

All Pages