CMPT 225 Lecture 5: Lecture 5
25 Jan 2019
School
Department
Course
Professor
Document Summary
A complete binary tree ( shape invariant ), invariant meaning doesn t change. Vertices labelled by key (our priority) values s. t. key(v) >= key(parent(v)) 7 this is our data structure for implementing an efficient priority queue. Add new node, where the shape changes, to maintain complete b. t. fix ordering priority. 2 9 when we switch 5 and 2, or any node, can only make parent smaller therefore, the other child of the parent must be bigger since it would have previously been checked. Trickle up v new node while(v not root and key(v) < parent(v)){ Heap removal (extract min) swap keys of vand parent(v) v parent(v) Move rightmost element of lewest level to the root trickle down from the root c childe with min key swap v with c. Basis: if h = 0 then there is 1 node (the root) and 2h+1 -1 = 20+1 -1 = 1, which is correct.
