CS 2110 Lecture Notes - Lecture 16: Priority Queue, Binary Tree, Southwest Ohio Regional Transit Authority
14 Jun 2017
School
Department
Course
Professor
Document Summary
Lecture 16 - heaps: abstract data structures vs concrete data structures. Adding to anywhere takes time proportional to length of list. Adv. getting something at position i takes constant time. Adding to beginning of list is a constant time. Getting something at position i takes time proportional to i: so arraylist and linkedlist are concrete data structures, some others. Only add at end, remove from beginning: abstract data structures are essentially interfaces. Implements iterable: today we are going to implement a priority queue and heaps. Priority queue - a bag in which data items are comparable. Essentially compare elements in the queue to determine order. Examples: interface priorityqueue { boolean add void clear. Unordered list add() put element at front o(1) poll() must search the list o(n) peek() must search the list o(n) Ordered (prioritized) add() o(n) has to search list to find where to insert it poll() min element at front o(1)
