Class Notes (839,458)
Canada (511,348)
CSC263H1 (54)
Lecture 2

Lecture 2.docx

3 Pages

Computer Science
Course Code
Toniann Pitassi

This preview shows page 1. Sign up to view the full 3 pages of the document.
Abstract data type: object + operations(OPS) - does not tell you how to implement it Data Structure: specific implementation of an ADT Example: ADT: Priority queues (PQ) Object: Set of elements with keys 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) Some simple data structures for priority queues: - Unordered linked list - Insert(s,x) : Ɵ (1) - Max(s) : Ɵ (n) - Ordered Linked List - Insert(s,x): Ɵ (n) - Max(s): Ɵ (1) We want Insert(s,x) : Ɵ (log n) and Extract_Max(s) : Ɵ (log n) and Max: Ɵ (1) Visual Description: A Complete Binary Tree : 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 2log n⌋ 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. For Example - S = 3, 4, 5, 7, 7, 9, 9, 12, 17 Since the tree is not unique, one example of S turning into a tree would be:[17, 9, 12, 7, 7, 9, 5, 3, 4] Putting the elements into a tree in order TLR Let A be an array that is heapified : index: 1 2 3 4 5 6 7 8 9 A: 17 9 12 7 7 9 5 3 4 Left Child of A[i] is A[2i] RIght child of A[i] is A[2i+1] Parent of A[i] is A[⌊i/2⌋] Heap Ops: - Keep the shape(CBT) - Max heap property has to be satisfied (A) Insert(A, x), Let's say Insert(A, 13) 1) increment the heap size
More Less
Unlock Document

Only page 1 are available for preview. Some parts have been intentionally blurred.

Unlock Document
You're Reading a Preview

Unlock to view full version

Unlock Document

Log In


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.