Class Notes (839,458)
CSC263H1 (54)
Lecture 2

Lecture 2.docx

3 Pages
62 Views

Department
Computer Science
Course Code
CSC263H1
Professor
Toniann Pitassi

This preview shows page 1. Sign up to view the full 3 pages of the document.
Description
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

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

Unlock Document

Unlock to view full version

Unlock Document
Me

OR

Join OneClass

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

Join to view

OR

By registering, I agree to the Terms and Privacy Policies
Just a few more details

So we can recommend you notes for your school.