CSI 2110 Lecture Notes - Lecture 7: Moveon.Org
7 Nov 2017
School
Department
Course
Professor
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.
