CS2110 Prelim #2 - BST, Heaps, Priority Queue, Maps, Sets

BST find()

Use compareTo()

BST add() - value isn’t there

follow comparisons and add normally

BST add() - value is there + right subtree is open

add same value at the right subtree after comparisons are followed

BST add() - value is there, but right subtree is occupied

• Go right once and then as far left as possible (also called a sucessor)

• Insert at empty left subtree

BST remove() general first step

Find the node you want to remove using find()

BST remove() ~ its right subtree is empty

Slide its left subtree up to replace it (supplanting)

**also works if the node is a leaf

BST remove() ~ its right subtree is non empty

• Copy sucessor’s value into node you’re trying to remove

• Slide og sucessor’s right subtree up

priority queue

thing with the highest priority gets removed first

heap

a data structure we can use to implement it

2 rules of max heaps

• Shape: fill levels from top to bottom, left to right

• Every parent must be >= each of its children

  • Siblings don’t need to be sorted

What is a heap stored in and how?

A heap is stored in an ArrayList level by level, left to right

Parent(i) =

(i-1)/2

leftChild(i) =

2 * i + 1

rightChild(i)

2 * i + 2

Maximum is always at what index?

0

Adding to the max heap [add()]

1. Put the new value in the next open position

2. Swap with its parent if its larger (called bubbleUp, repeat as many times as needed)

Removing from the max heap [remove()]

1. Remove root and replace with the last element

2. Compare the new root with its smaller child (repeat as many times as needed and swap if needed)

3. Called bubbleDown()

Priority queue stores what…

item + priority

Heap sorted by what…

priority #

Heapsort

1. heapify: rearrange array into a max heap

2. repeatedly move maximum to the end of remaining heap

Basic rules for sets

Distinct elements, duplicates don’t count; sets also have no meaningful positions.

Union

Set with everything in either set (no repeated elements)

Restriction

Only keep items that pass a predicate

Intersection

keep only elements in BOTH sets

Maps

Use a key to look up a value

Keys MUST be what ___ and values can what ____

unique, repeat

What happens if you try to add a duplicate key

the existing key will be replaced

Searching examines each entry’s ___, not its value

key

Dynamic priority queues

Combine maps with heaps so you can change an element’s priority after adding it.

How do DPQs work

1. use map to find its heap index

2. change its priority

3. if priority increased, bubble up

4. if priority decreased, bubble down