ZuoTi.Pro
Question

In the lectures, we studied binary heaps. A min-Heap can be visualized as a binary tree of height with each node having at most two children with the property that value of a node is at most the value of its children. Such heap containing n elements can be represented (stored) as an array with the property Suppose that you would like to construct a & min Heap: each node has at most& children and the value of a node is at most the value of its children (a) How do you represent& min heap as an array? Write the property of the array. (b) What is the height of the heap (when visualized as a tree) consisting of n elements in terms of l and n? Assume that the height of a heap-tree with just 1 element is 1. (c) Describe an algorithm to remove the smallest element from an & heap containing n elements. What is the asymptotic run time of the your algorithm (in terms of n and Part of the grade depends on the runtime.

engineering   Computer-Science   
0 0
Add a comment Improve this question Transcribed image text
Next > < Previous
Sort answers by oldest

Homework Answers

Answer #1

s uppose, hergh 2-3 etemets elements →2 elements S) (6 ) (7 h+ h+l Taking oon both ides e need to conaider heiaht heght is more in ou aoe eloments -1 S

0 0
Add a comment
Know the answer?
Add Answer to:
In the lectures, we studied binary heaps. A min-Heap can be visualized as a binary tree...
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for? Ask your own homework help question. Our experts will answer your question WITHIN MINUTES for Free.
Similar Homework Help Questions

  • Trees and Heaps 1. Show that the maximum number of nodes in a binary tree of...

    Trees and Heaps 1. Show that the maximum number of nodes in a binary tree of height h is 2h+1 − 1. 2. A full node is a node with two children. Prove that the number of full nodes plus one is equal to the number of leaves in a nonempty binary tree. 3. What is the minimum number of nodes in an AVL tree of height 15? 4. Show the result of inserting 14, 12, 18, 20, 27, 16,...

  • What is the difference between the binary-search-tree property and the min-heap property (see page 129)? Can...

    What is the difference between the binary-search-tree property and the min-heap property (see page 129)? Can the min-heap property be used to print out the keys of an n-node tree in sorted order in O(n) time? Explain how or why not.

  • Suppose that binary heaps are represented using explicit links. Give a simple algorithm to find the...

    Suppose that binary heaps are represented using explicit links. Give a simple algorithm to find the tree node that is at implicit position i. instructions: provide Java-like pseudocode. The implicit position of a node refers to the index it would have if the heap was stored in the array format reviewed in class (first element at index 1).

  • 1. What is the worst case time complexity of insertion into a binary search tree with...

    1. What is the worst case time complexity of insertion into a binary search tree with n elements? You should use the most accurate asymptotic notation for your answer. 2. A binary search tree is given in the following. Draw the resulting binary search tree (to the right of the given tree) after deleting the node with key value 8. 10 3. You have a sorted array B with n elements, where n is very large. Array C is obtained...

  • 6. T or F: There can be two or more nodes in a heap with exactly...

    6. T or F: There can be two or more nodes in a heap with exactly one child. 7. T or F: A heap can have no nodes with exactly one child. 8. T or F: All heaps are perfect trees. 9. T or F: No heaps are perfect trees. 10. T or F: All heaps are complete trees. 11. T or F: No heaps are complete trees. 12. T or F: A binary tree with one node must be...

  • In class, we discussed the priority queue (PQ) ADT implemented using min-heap. In a min-heap, the...

    In class, we discussed the priority queue (PQ) ADT implemented using min-heap. In a min-heap, the element of the heap with the smallest key is the root of the binary tree. On the other hand, a max-heap has as root the element with the biggest key, and the relationship between the keys of a node and its parent is reversed of that of a min-heap. We also discussed an array-based implementation of heaps. In this assignment, your task is to...

  • A heap can be encoded either as an array, or as a full binary tree. For...

    A heap can be encoded either as an array, or as a full binary tree. For this question, write a function that takes the array representation of a heap and outputs its binary tree representation. More specifically, you should write a function with the specifications given below. Specifications for the function: # def arrayToTree(A, j): # input: array A representing a heap, an index j in [0:len(A)] # output: a Node object storing the heap with root j in the...

  • C++ Question 5 5 pts In a min-heap of N elements, if we want to find...

    C++ Question 5 5 pts In a min-heap of N elements, if we want to find the max element, we have to search all the leaves. What is the big-o running time of findMax? O(N^2) Oſlog N) O(N) OIN log N) Question 6 5 pts An AVL tree is a Binary Search Tree that has the following additional property for every node in the tree, the height of the left and right subtrees is the same none of the above...

  • 5. A three-heap with n elements can be stored in an array A, where A[O] contains...

    5. A three-heap with n elements can be stored in an array A, where A[O] contains the root of the tree. a) Draw the three-heap that results from inserting 5, 2, 8, 3, 6, 4, 9, 7, 1 in that order into an initially empty three-heap. You do not need to show the array representation of the heap. You are only required to show the final tree, although if you draw intermediate trees. b) Assuming that elements are placed in...

  • 1. Which of the following is a proper array representation a binary min heap?

    1. Which of the following is a proper array representation a binary min heap?2. A heap is implemented using an array. At what index will the right child of node at index i be found? Note, the Oth position of the array is not used.Select one:a. i/2b. 2 i+1c. i-1d. 2 i3. Consider the following array of length 6. Elements from the array are added, in the given order, to a max heap. The heap is initially empty and stored as an array.A={18,5,37,44,27,53}What...

ADVERTISEMENT
Free Homework Help App
Download From Google Play
Scan Your Homework
to Get Instant Free Answers
Need Online Homework Help?
Ask a Question
Get Answers For Free
Most questions answered within 3 hours.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT