CSI 2110 Lecture Notes - Lecture 7: Moveon.Org

38 views1 pages

Document Summary

Complete binary trees (all levels are full except last which is left filled) Store a collection of keys or key-element pairs at internal nodes. The height of a heap storing n keys has height o(log n) Downheap compares the parent with the smallest child. If the child is smaller, it switches the two. Terminates when the key is greater than the keys of both of its children or the bottom on the heap is reached. The key to be inserted is added to the next available position in the heap. Parent-child keys that are out of order are swapped. Upheap terminates when the new key is greater than the key of its parent or the top of the heap is reached. Idea: recursively re-arrange each subtree in the heap starting with the leaves. Switch starting from the bottom, work your way up to bigger subtrees and rearrange them. Construct a tree with the number of nodes you need to insert.

Get access

Grade+20% off
$8 USD/m$10 USD/m
Billed $96 USD annually
Grade+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
40 Verified Answers
Class+
$8 USD/m
Billed $96 USD annually
Class+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
30 Verified Answers

Related Documents