CSE 373 Section 5: Heaps and Midterm Review
In this session, students cover Heaps and delve into a Midterm Review. The agenda includes understanding Heaps, operations like Percolating, and Array Representations. Problem sets guide students on inserting elements into a MinHeap and understanding parent relationships. Detailed visual aids enhance learning, making the session engaging and informative for students preparing for their Midterm.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
CSE 373 Section 5 Heaps + MT Review
Logistics and Section Agenda - - - P2 due yesterday P3 Heaps releases today (due in 2 weeks) Today s section will cover: - 35% Heaps (worksheet: sec05.pdf) - 65% Midterm review (worksheet: midtermreview.pdf)
Operations Percolate up!
Operations Need to replace with something .
Operations Percolate down!
Problem 2a Insert 10, 7, 15, 17, 12, 20, 6, 32
Problem 2a Insert 10, 7, 15, 17, 12, 20, 6, 32 10 Underlying array: [N, 10, N, N, N, N, N, N, N] 0 1 2 3 4 5 6 7 8
Problem 2a Insert 10, 7, 15, 17, 12, 20, 6, 32 10 7 Percolate inserted node up! Underlying array: [N, 10, 7, N, N, N, N, N, N] 0 1 2 3 4 5 6 7 8
Problem 2a Insert 10, 7, 15, 17, 12, 20, 6, 32 10 Am I smaller than parent? 7 Underlying array: [N, 10, 7, N, N, N, N, N, N] 0 1 2 3 4 5 6 7 8
Problem 2a Insert 10, 7, 15, 17, 12, 20, 6, 32 10 Am I smaller than parent (which is at i/2)? 7 Underlying array: [N, 10, 7, N, N, N, N, N, N] 0 1 2 3 4 5 6 7 8
Problem 2a Insert 10, 7, 15, 17, 12, 20, 6, 32 7 Swap! 10 Underlying array: [N, 7, 10, N, N, N, N, N, N] 0 1 2 3 4 5 6 7 8
Problem 2a Insert 10, 7, 15, 17, 12, 20, 6, 32 7 insert(15) 10 15 Underlying array: [N, 7, 10, 15, N, N, N, N, N] 0 1 2 3 4 5 6 7 8
Problem 2a Insert 10, 7, 15, 17, 12, 20, 6, 32 7 Percolate up 10 15 Underlying array: [N, 7, 10, 15, N, N, N, N, N] 0 1 2 3 4 5 6 7 8
Problem 2a Insert 10, 7, 15, 17, 12, 20, 6, 32 7 insert(17) 10 15 17 Underlying array: [N, 7, 10, 15, 17, N, N, N, N] 0 1 2 3 4 5 6 7 8
Problem 2a Insert 10, 7, 15, 17, 12, 20, 6, 32 7 Percolate up 10 15 17 Underlying array: [N, 7, 10, 15, 17, N, N, N, N] 0 1 2 3 4 5 6 7 8
Problem 2a Insert 10, 7, 15, 17, 12, 20, 6, 32 7 insert(12) and percolate up 10 15 17 12 Underlying array: [N, 7, 10, 15, 17, 12, N, N, N] 0 1 2 3 4 5 6 7 8
Problem 2a Insert 10, 7, 15, 17, 12, 20, 6, 32 7 insert(20) and percolate up 10 15 17 12 20 Underlying array: [N, 7, 10, 15, 17, 12, 20, N, N] 0 1 2 3 4 5 6 7 8
Problem 2a Insert 10, 7, 15, 17, 12, 20, 6, 32 7 insert(6) and percolate up 10 15 6 17 12 20 Underlying array: [N, 7, 10, 15, 17, 12, 20, 6, N] 0 1 2 3 4 5 6 7 8
Problem 2a Insert 10, 7, 15, 17, 12, 20, 6, 32 7 Swap 6 with 15 10 6 15 17 12 20 Underlying array: [N, 7, 10, 6, 17, 12, 20, 15, N] 0 1 2 3 4 5 6 7 8
Problem 2a Insert 10, 7, 15, 17, 12, 20, 6, 32 6 Swap 6 with 7 10 7 15 17 12 20 Underlying array: [N, 6, 10, 7, 17, 12, 20, 15, N] 0 1 2 3 4 5 6 7 8
Problem 2a Insert 10, 7, 15, 17, 12, 20, 6, 32 6 Percolate done 10 7 15 17 12 20 Underlying array: [N, 6, 10, 7, 17, 12, 20, 15, N] 0 1 2 3 4 5 6 7 8
Problem 2a Insert 10, 7, 15, 17, 12, 20, 6, 32 6 Insert 32 and percolate 10 7 15 17 12 20 Underlying array: [N, 6, 10, 7, 17, 12, 20, 15, 32] 0 1 2 3 4 5 6 7 8 32
Midterm Review Time Cast your votes per topic: Zoom -> Participants -> yes if interested in topic - - - - - - - ADT & Data Structures 7 Algorithmic Analysis 5 Recursive Algorithmic Analysis 5 Hash Maps 1 BSTs and AVL Trees 2 Memory Characteristics and Caching 2 Miscellaneous?
