CMPSC 24 Lecture Notes - Lecture 17: Binary Tree, Binary Search Tree, Priority Queue
Document Summary
Perfect binary tree = all leaves are at the same level and every nonleaf node has two children. Complete binary tree = either perfect or perfect through the next-to-last level. Leaves on the last level are as far to the left as possible. Encode a complete binary tree in an array. Heap (minheap) = binary tree that satisfies special shape and order properties. Order: for each node in the heap, the value stored in that node is at most the value in each of its children. The parent is the minimum; less than or equal to children. Add v to the next empty position in the heap. Else swap(v, parent(v)) percolateup(v) towards the root to maintain the order property. Don"t remove the root itself, just the element. Move the last element in the heap to the root. Maintains the complete binary tree structure shape percolatedown() Find the minimum element among the children and swap.
