CSC263H1 Lecture 3: Lecture 3.docx
22 Apr 2014
School
Department
Course
Professor
Document Summary
K 0: sk- trees has 2^k nodes. There are (k d) nodes at depth d. Def: a binomial forest of size n (bfn) is a sequence of sk trees with strictly decreasing k"s and a total of n nodes. Ex: a bf of n = 7 nodes. Bf7 = n = 2^2 + 2^1 + 2^0 = <1 1 1>2. Ex: a bf of n = 9 nodes. Bf9 = n = 2^3 + 2^0 = <1 0 0 1>2. A bfn where n = 2. Bfn = < sk trees such that bk= 1> Let (n) = # of 1"s in the binary rep of n: bfn has (n) trees, bfn has n - (n) edges. A (min) binomial heap of n elements with keys is a bfn such that: each node of bfn stores one element, each sk tree of the bfn is min heap ordered.
