8.5.2 Physical Structure of a Heap The nodes of a heap are stored physically in an x array. The root of the tree is in the first element of x the array. The children of the node at location are at locations and n 2n 2n + 1. x The parent of the node at location is at location . x n n/2 8.5.3 Building a Heap A heap is built by inserting elements at the end of the heap, as a new leaf, and x then "sifting up," sorting the branch from the new leaf to the root. Example: x x Insert R Insert R L R: L: x x R L Sift L R L: x x L R Insert L R C x C: Sift C R L x C: Insert C R L A A: x Sift A C L R A: x Insert A C L R H H: x
8.5.2 Physical Structure of a Heap x The nodes of a heap are stored physically in an array. x The root of the tree is in the first element of the array. x The children of the node at location n are at locations 2n and 2n + 1. x The parent of the node at location n is at location n/2 . 8.5.3 Building a Heap x A heap is built by inserting elements at the end of the heap, as a new leaf, and then "sifting up," sorting the branch from the new leaf to the root. x Example: x Insert R: R x Insert L: R L x R L x Sift L: L R x L R x Insert C: L R C x Sift C: C R L x Insert A: C R L A x Sift A: A C L R x Insert H: A C L R H