CSC263H1 Lecture Notes - Lecture 2: Longest Path Problem, Binary Tree, Heapsort
22 Apr 2014
School
Department
Course
Professor
Document Summary
Does not tell you how to implement it. Ops: insert (s, x) : s s {x} Max (s): return an element with max priority from s. Extract_max: returns max(s) and s s - max(s) We want insert(s,x) : (log n) and max: (1) Root node is level 0, 2^0 = 1. Every level l, except possibly the last one has 2^l nodes. At the bottom level, all nodes are as far to the left as possible. The complete binary tree above has 9 nodes(n = 9). A cbt with n nodes has height of log . Height(t) = length of the longest path from the root of t to a leaf. Max_heap: the n elements of s are stored in a cbt of n nodes such that : Priority of each node priority of its children. S = 3, 4, 5, 7, 7, 9, 9, 12, 17.
