COMP 250 Lecture Notes - Lecture 24: The Algorithm, David Jude Jolicoeur, Quotient Rule
7 Nov 2016
School
Department
Course
Professor
Document Summary
Heaps 3 __________________ (1) new algorithm for buildheap. Instead of sequentially adding the elements into the array and moving them up the heap, do something different. That doesn"t do much other than say that the list is represented by an array. Then, rather than starting from 1 and adding i from i=1 ton, we will start from n/2, and move downwards i. Start with k=size/2, and decrease k, and bubble stuff down . So instead of starting from 1 i and moving things up, start at size/2, and move things down. Threw letters into a tree, and we want to build a heap from this. Start at n/2, so in this case n=6, so start at k=3 (t). We are concerned about the t being bigger than its children. In this case, t is bigger than f, which is a problem. The size" we pass into downheap() in this algorithm will alway be the size of the tree.
