CSE 373 SP24 AX: Section 5

Heaps and Hashing

Warm Up: What are the operations that take place when removing the root in this max-heap? What does the final heap look like?

9

8

2

6

5

1

Options (On the Worksheet)

Warm Up: What are the operations that take place when removing the root in this max-heap? What does the final heap look like?

8

5

2

6

1

6

8

2

1

5

8

2

1

6

5

1

8

2

6

5

A

B

C

D

9

8

2

6

5

1

Max Heap Solution

8

5

2

6

1

9

Steps:

• Swap the root with the leaf node closest to the right.

Array Representation

Idx

Val

Max Heap Solution

8

5

2

6

9

Steps:

• Swap the root with the leaf node closest to the right.
• Remove the leaf node 9, which was previously the root

1

Array Representation

Idx

Val

Max Heap Solution

8

5

2

6

1

Steps:

• Swap the root with the leaf node closest to the right.
• Remove the leaf node 9, which was previously the root
• Sink!

​

Compare child nodes to curr node, for the max

Array Representation

Idx

Val

Max Heap Solution

8

5

2

6

1

Steps:

• Swap the root with the leaf node closest to the right.
• Remove the leaf node 9, which was previously the root
• Sink!

​

Compare child nodes to curr node, for the max

Array Representation

Idx

Val

Max Heap Solution

8

5

2

6

1

Steps:

• Swap the root with the leaf node closest to the right.
• Remove the leaf node 9, which was previously the root
• Sink!

​

Sink to the max child

Array Representation

Idx

Val

Max Heap Solution

8

5

2

6

1

Steps:

• Swap the root with the leaf node closest to the right.
• Remove the leaf node 9, which was previously the root
• Sink!

​

Compare again!

Array Representation

Idx

Val

Max Heap Solution

8

5

2

6

1

Steps:

• Swap the root with the leaf node closest to the right.
• Remove the leaf node 9, which was previously the root
• Sink!

​

Sink!

Array Representation

Idx

Val

Max Heap Solution

8

5

2

6

1

Steps:

• Swap the root with the leaf node closest to the right.
• Remove the leaf node 9, which was previously the root
• Sink!

​

DONE!

Array Representation

Idx

Val

Binary Heap Overview

• A Priority Queue ADT Implementation - A Data Structure
• add(value), removeMin(), peekMin()
• Min Heap Invariant: Every node is less than or equal to all its children
• Complete Tree Invariant: A heap is always a complete tree
• Every level, except possible the bottom level, is completely full
• The bottom level is filled from left to right with no gap! Remember to swim/percolate up!
• Binary heap height bounds at Θ( log(n) )
• Binary Tree Invariants: Every node has at most 2 children
• A binary heap needs to satisfy all three invariants above

​

Questions?

Check-In

• Ask us a question!

(unrelated to CS pls)

​

​

• How many midterms do you have coming up?

Announcements

• Lectures: Affordance Analysis (tomorrow) - do pre-lecture reading + quiz!
• Project: Autocomplete analysis due tomorrow night!
• Exercise 4 is out due EOD Tuesday 4/30, peer review by 5/5
• Remember that you need to submit a resub form (linked on Ed) and resubmit again to Canvas to be eligible for a resubmission.
• You can now resubmit any two exercise problems per week!

Micro-teach: Hashing

Hash Tables

One way to implement the dictionary/Map ADT.

​

Stores item with key x in array index (or “bucket”) h(x).�(The choice of h(x)is important for many reasons.)��

In this case h(x) = x; but this is NOT always the case

HashTable Example (On the Worksheet)

Hash Code: (string length)

For this example, the underlying array has size 4.

Draw what the hashmap looks like after lines 1-5 have been run.

HashTable Example Intermediate States

Code lines 1-5

HashTable Example

Hash Code: (string length)

For this example, the underlying array has size 4.

Draw what the hashmap looks like after lines 1-9 have been run.

HashTable Example Intermediate States

Code lines 1-9

HashTable Example

Hash Code: (string length)

For this example, the underlying array has size 4.

Draw what the hashmap looks like after all lines have been run.

HashTable Example

Final State:

HashTable Example

Hash Code: (string length)

For this example, the underlying array has size 4.

What does map.size() return?

HashTable Overview

• How do we handle collisions?
• There are many ways! Ex. jumping forward until we find an empty bucket, using another algorithm to find the next available spot…
• Common solution; use separate chaining (shown in previous example)
• How do we choose a hash function?
• Goal; no collisions!!
• How to achieve this? You want the hash function to distribute the keys evenly.
• How does this affect runtime??
• Best Case: No collisions, operations in constant time
• Worst Case: N Collisions in the bucket or resize, operations in N time

Questions?

Case Study #4: Augmentative and Alternative Communication (AAC)

What is an AAC?

Augmentative and Alternative Communication (AAC)

• Augmentative: add to someone’s speech/signing
• Alternative: used instead of speech/signing

​

• Click/push buttons on picture/text icons that will be read out loud (think text-to-speech). Some icons are categories that lead to more icons and more choices.

​

• Temporary vs. throughout life situations

​

​

Design Considerations: Motor Plans

Reducing the need to learn many different motor plans

• A speech pathologist may want to mimic acquiring language, by hiding words from the display, when helping someone learn an AAC
• When you were a child learning speech, you tend to filter out big words you don’t know as well.
• But we should maintain a good layout for the words/phrases that will work later on without causing a largely different motor plan.
• It would be hard if the layout of our own computer keyboard would change!

​

​

​

Design Considerations: Common Words/Phrases

Access to common words/phrases quickly

• Frustrating for the user to go through many motions to access a commonly used word/phrase.

​

​

Designing an AAC: HashMap

Should we use a recursive HashMap? Think about this design using a HashMap:

• When displaying the AAC, we could iterate over the hashmap to display they <key, value> pairs into the 2D grid interface format.

​

class AAC {

HashMap<Button, AAC> grid;

}

​

Designing an AAC: Fundamentals

What is a problem of using a recursive HashMap solution?

​

Remember the design features we want to build in:

• Reducing the need to learn many different motor plans
• Access to common words/phrases quickly

​

If we iterate over the recursive HashMap to create the 2D grid for the interface, we will get a different order for the layout everytime! A new motor plan each time!

• HashMaps are not ordered! The hashing strategy is meant to place objects in a pseudo-random order (into the buckets), to optimize quick placement and look-up time.

​

Designing an AAC: Fundamentals

What is a problem of using a recursive HashMap solution?

​

Remember the design features we want to build in:

• Reducing the need to learn many different motor plans
• Access to common words/phrases quickly

​

​

​

Designing our AAC

Let’s use a recursive 1D Array approach instead where each box index contains three fields: text, image, display (for hiding words) and a pointer to the next 1D array.

Access to common words/phrases quickly

Remember the design features we want to build in:

• Reducing the need to learn many different motor plans
• Access to common words/phrases quickly

​

Let’s Design!

​

commonWords

Choose a data structure + write out an approach in a few English sentences. What is the runtime?

​

commonWords(List<String> words)

• words: A long long list of utterances/speech from many different humans.
• Ex: {"the", "uhh", "hi", “good morning”, “the”, “hi”, “hello world”, “hi”}
• Returns: The top 50 most common words/phrases a human uses arranged in a 1D array, to add to a separate page of the AAC for easy access.
• count up and sort what words/phrases are used in words and put into 1D array.

How would we integrate this into the AAC design we made earlier?

​

​

​

​

Connecting back to the AAC

• Add all 50 words to the top-level button on the interface
• Selecting the button leads to a new interface with the 50 words

Project Priority Queues Overview

• Implementation: UnsortedArrayMinPQ, HeapMinPQ, OptimizedHeapMinPQ
• Explain the parts of HeapMinPQ and OptimizedHeapMinPQ you're most proud of.
• Length of time tends to increase with each implementation task.
• ReportAnalyzer for Web Content Accessibility Guideline (WCAG)
• Analyze and compare
• Asymptotic Analysis:
• Analyze the Big-Θ bound for worst-case runtime of removeMin and changePriority
• Analyze usage of Tree bucket optimization in Hash table
• Random Testing

Include each DELIVERABLE in your presentation!

Closing Announcements

• Thanks for coming to section! See you tomorrow in class! Stay safe and stay hydrated :)
• Turn in today’s worksheet + section reflection + lecture worksheets in by Sunday!
• Turn in the resubs if you have any! You can submit two exercises problems!
• Remember analysis for Autocomplete is due tomorrow night!

​

​

Please don't hesitate to reach out if you have any

questions or concerns about the course, or if there's

anything else we can help you with! We're here to support

you however we can!