CSE 373 SP25 AX: Section 5

Heaps and Hashing

9

8

2

6

5

1

Announcements

• Exam Resubmissions: Submit Exam resubmissions by Friday May 2nd 12:30 PM!
• Deques Resubmissions: Due by Friday May 2nd 11:59 PM!
• Ed Post #131

Micro-teach: Heaps

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

​

Question 1 (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

Q1 Solution

8

5

2

6

1

9

Steps:

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

Array Representation

Idx

Val

Note: Make sure you understand the array representation here too! :)

Q1 Solution

8

5

2

6

9

Steps:

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

1

Array Representation

Idx

Val

Note: Make sure you understand the array representation here too! :)

Q1 Solution

8

5

2

6

1

Steps:

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

​

Compare child nodes to curr node, for the max

Array Representation

Idx

Val

Note: Make sure you understand the array representation here too! :)

Q1 Solution

8

5

2

6

1

Steps:

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

​

Compare child nodes to curr node, for the max

Array Representation

Idx

Val

Note: Make sure you understand the array representation here too! :)

Q1 Solution

8

5

2

6

1

Steps:

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

​

Sink to the max child

Array Representation

Idx

Val

Note: Make sure you understand the array representation here too! :)

Q1 Solution

8

5

2

6

1

Steps:

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

​

Compare again!

Array Representation

Idx

Val

Note: Make sure you understand the array representation here too! :)

Q1 Solution

8

5

2

6

1

Steps:

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

​

Sink!

Array Representation

Idx

Val

Note: Make sure you understand the array representation here too! :)

Q1 Solution

8

5

2

6

1

Steps:

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

​

DONE!

Array Representation

Idx

Val

Note: Make sure you understand the array representation here too! :)

Extra Practice: Min-Heap Values

Assume the integers 1-11 were inserted into the min-heap below in an unknown order.

What are all the possible nodes (A-K) where you could find each of the numbers below? Explain your reasoning for both the places you could find each number and the places you could not find each number.

1. The number 11 (the largest value)
2. The number 6 (the median value)
3. The number 3

​

Extra Practice: Min-Heap Values (hint)

• Min-heap invariant: The value of a node must be less than or equal to the values of all its children.

≤ D,J (*and all their children)

≤ B,F*

≤ I,K*

≤ A,C*

≤ E,G*

Questions?

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 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

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?

2. Assume Point(1, 2) is put into an empty hash table with M = 2 buckets using Point.hashcode.

If two points are equal if and only if their x-values are equal, what would calling contains(Point(1, 3)) on the hash table return?

Explain your answer by explaining how contains uses both the hashCode and equals methods to search for objects.

Hashing Points (Extra Practice)

1. Mark all the points that will collide with Point(1, 2) on a hash table with M = 2 buckets.

Explain why each point does or does not collide by using its hashCode to find the index of its bucket.

• Point(1, 1)
• Point(2, 1)
• Point(3, 1)

• Point(1, 3)
• Point(1, 4)
• Point(1, 5)

public boolean equals(Object o) {

Point other = (Point) o;

return this.x == other.x;

}

• true
• false
• Not enough info

public class Point {

public final int x, y;

​

public Point(int x, int y) {

this.x;

this.y;

}

​

public int hashCode() {

return this.x + this.y;

}

}

Questions?

Gradescope: Autocomplete

AND ON YOUR WORKSHEET!

Closing Announcements

• Thanks for coming to section! Stay safe and stay hydrated :)
• Get in your Deques Regrade Request by Friday!
• Get in your Exam 1 Resubmission by Friday!

​

​

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!