Class Notes (806,820)
Canada (492,456)
CMPT 225 (60)
John Edgar (28)
Lecture 6

CMPT 225 Week 6 Lecture 2

2 Pages
Unlock Document

Simon Fraser University
Computing Science
CMPT 225
John Edgar

Priority QueueADT First thing to be removed is item with highest priority Could be lowest first or highest first Actual priority could be based on anything you want Inserting and remove in at most O(log n) time. Removal must be done in priority order. Removal can only be done efficiently if ordered in some way Could use a balanced binary search tree BSTs are fully ordered and insertion and removal can be implemented in O(log n) time Operations complex (esp removal), though, and require a lot of structural overhead Much simpler binary tree solution Heap ADT Complete, partially ordered, binary tree Common implementation of a priority queue Implementing ADT with anADT Tree: Connected graph made up of nodes and edges Exactly one less edge than number of nodes Tree has root - first node Tree has leaves - nodes with no children Binary tree - at most 2 children per node Nodes == vertices/vertexes In trees, nodes are only connected to 3 other nodes at most - parent and 2 children Complete: all levels except bottom are completely filled in. Leaves on bottom are as far to the left as possible. (every node has two children other than bottom) Partially ordered: value of every node is greater than or equal to children. Full ordered tree is different. In order traversal (walking through the tree) [go to left, visit, go right], visit every single node in tree, go left first
More Less

Related notes for CMPT 225

Log In


Don't have an account?

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.