Class Notes (1,100,000)
US (490,000)
Cornell (1,000)
CS (100)
CS 2110 (30)
Gries (30)
Lecture 16

CS 2110 Lecture Notes - Lecture 16: Priority Queue, Binary Tree, Southwest Ohio Regional Transit Authority


Department
Computer Science
Course Code
CS 2110
Professor
Gries
Lecture
16

This preview shows page 1. to view the full 4 pages of the document.
Lecture 16 - Heaps
oAbstract data structures vs concrete data structures
Abstract - Interfaces
Defines a data type
Has various methods
Add, remove, get, …
Then you have classes implement it
Examples
ArrayList
Array
Disadv. Adding to anywhere takes time
proportional to length of list
Adv. getting something at position i takes constant
time
LinkedList
Chained nodes
Adv. Adding to beginning of list is a constant time
Disadv. Getting something at position i takes time
proportional to i
oSo ArrayList and LinkedList are Concrete data structures
oSome others
Stacks (LIFO) implemented using a List
Allows only add(0, val), remove(0)
Push, pop
Queue
Only add at end, remove from beginning
oAbstract Data Structures are essentially interfaces
Example: Bag
Implements iterable
oToday 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
Each element has some priority
Examples:
interface PriorityQueue<E> {
boolean add
void clear
E peek
E poll
boolean contains
Boolean remove
Int size()
Iterator<E> iterator()
}
find more resources at oneclass.com
find more resources at oneclass.com
You're Reading a Preview

Unlock to view full version