Introduction to CSE 373 Data Structures and Algorithms with Heaps

cse 373 sp 18 kasey champion n.w
1 / 22
Embed
Share

Explore the world of CSE 373 Data Structures and Algorithms with a focus on heaps. Learn about Priority Queue ADT, AVL trees, and Binary Heaps. Gain insights into operations like removeMin, peekMin, insert, and more. Discover how to optimize operations for best-case scenarios. Dive into the fundamentals of heap structures in this engaging lecture.

  • Data Structures
  • Algorithms
  • Heaps
  • Priority Queue
  • AVL Trees
rayaanacharya
roer605 Follow

Uploaded on | 0 Views

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.

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

E N D

Presentation Transcript

  1. CSE 373 SP 18 - KASEY CHAMPION Lecture 12: Intro to CSE 373 Data Structures and Algorithms Heaps 1

  2. Administrivia HW 3 due day extended until Tuesday February 12th due to snow Extra office hours over the next few days HW 4 released Friday February 8th due Friday February 15th CSE 373 SP 18 - KASEY CHAMPION 2

  3. Heaps CSE 373 SP 18 - KASEY CHAMPION 3

  4. Priority Queue ADT Imagine you have a collection of data from which you will always ask for the extreme value Min Priority Queue ADT Max Priority Queue ADT state state Set of comparable values - Ordered based on priority state state Set of comparable values - Ordered based on priority If a Queue is First-In-First-Out (FIFO) Priority Queues are Most-Important-Out-First Example: Triage, patient in most danger is treated first behavior behavior behavior behavior removeMin removeMin() () returns the element with the smallest priority, removes it from the collection peekMin peekMin() () find, but do not remove the element with the smallest priority insert(value) insert(value) add a new element to the collection removeMax removeMax() () returns the element with the largest priority, removes it from the collection peekMax peekMax() () find, but do not remove the element with the largest priority insert(value) insert(value) add a new element to the collection Items in Queue must be comparable, Queue manages internal sorting CSE 373 SP 18 - KASEY CHAMPION 4

  5. Lets start with an AVL tree What is the worst case for peekMin()? O( O(logn logn) ) AVLPriorityQueue<E> state state overallRoot What is the best case for peekMin()? O(1) O(1) behavior behavior removeMin() traverse through tree all the way to the left, remove node, rebalance if necessary Can we do something to guarantee best case for these two operations? peekMin() traverse through tree all the way to the left insert() traverse through tree, insert node in open space, rebalance as necessary CSE 373 SP 18 - KASEY CHAMPION 5

  6. Binary Heap A type of tree with new set of invariants 1. 1. Binary Tree Binary Tree: every node has at most 2 children 2. 2. Heap Heap: every node is smaller than its child 3. 3. Structure: Structure: Each level is complete meaning it has no gaps - Heaps are filled up left to right 1 8 1 2 3 10 9 2 3 22 4 5 7 4 6 5 36 10 9 8 47 CSE 373 SP 18 - KASEY CHAMPION 6

  7. Self Check - Are these valid heaps? 3 Minutes INVALID Binary Heap Invariants: 1. Binary Tree 2. Heap 3. Complete 1 VALID 3 INVALID 4 4 7 5 6 2 5 6 9 7 8 8 7 3 10 9 11 CSE 373 SP 18 - KASEY CHAMPION 7

  8. Implementing peekMin() Runtime: O(1) Runtime: O(1) 2 7 4 10 9 5 8 11 13 CSE 373 SP 18 - KASEY CHAMPION 8

  9. Implementing removeMin() 1.) Return min 2.) replace with last added 13 2 7 7 4 4 10 10 9 9 5 5 8 8 11 11 13 Structure maintained, heap broken CSE 373 SP 18 - KASEY CHAMPION 9

  10. Implementing removeMin() - percolateDown 3.) percolateDown() Recursively swap parent with smallest child 13 4 7 4 13 5 10 9 5 11 13 8 11 13 CSE 373 SP 18 - KASEY CHAMPION 10

  11. 3 Minutes Practice: removeMin() 5 9 18 9 18 11 10 11 18 13 17 14 20 19 16 15 24 22 18 CSE 373 SP 18 - KASEY CHAMPION 11

  12. Implementing insert() Algorithm: - Insert a node to ensure no gaps - Fix heap invariant - percolate UP UP 2 7 4 3 10 9 5 8 3 4 11 3 7 13 CSE 373 SP 18 - KASEY CHAMPION 12

  13. 3 Minutes Practice: Building a minHeap Construct a Min Binary Heap by inserting the following values in this order: 5, 10, 15, 20, 7, 2 Min Binary Heap Invariants Min Binary Heap Invariants 1. 1. Binary Tree Binary Tree each node has at most 2 children 2. 2. Min Heap Min Heap each node s children are larger than itself 3. 3. Level Complete Level Complete - new nodes are added from left to right completely filling each level before creating a new one Min Priority Queue ADT state state Set of comparable values - Ordered based on priority 5 2 behavior behavior removeMin removeMin() () returns the element with the smallest priority, removes it from the collection peekMin peekMin() () find, but do not remove the element with the smallest priority 15 2 5 10 7 percolateUp percolateUp! ! insert(value) insert(value) add a new element to the collection 2 15 20 7 10 percolateUp percolateUp! ! percolateUp percolateUp! ! CSE 373 SP 18 - KASEY CHAMPION 13

  14. minHeap runtimes removeMin(): - Find and remove minimum node - Find last node in tree and swap to top level - Percolate down to fix heap invariant insert(): - Insert new node into next available spot - Percolate up to fix heap invariant CSE 373 SP 18 - KASEY CHAMPION 14

  15. Implementing Heaps How do we find the minimum node? ???????() = ???[0] A How do we find the last node? ????????() = ???[???? 1] B C How do we find the next open space? ?????????() = ???[????] How do we find a node s left child? E F G D ????? ??? ? = 2? + 1 How do we find a node s right child? J K L H I ??? ?? ??? ? = 2? + 2 How do we find a node s parent? ?????? ? =? Fill array in level level- -order order from left to right ? 1 2 2 ?????? ? = 0 0 0 0 1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4 5 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8 9 9 9 9 10 10 10 10 11 11 11 11 12 12 12 12 13 13 13 13 A A B B A A C C B B D D C C E E D D F F E E G G F F H H G G H H I I J J I I K K J J L L K K L L CSE 373 SP 18 - KASEY CHAMPION 15

  16. Heap Implementation Runtimes char peekMin() timeToFindMin A Tree Tree Array Array (1) (1) C B char removeMin() findLastNodeTime + removeRootTime + numSwaps * swapTime (n) Tree Tree n + 1 + log(n) * 1 F D E Array Array (log(n)) 1 + 1 + log(n) * 1 void insert(char) findNextSpace + addValue + numSwaps * swapTime 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 A A B B C C D D E E F F (n) n + 1 + log(n) * 1 Tree Tree (log(n)) Array Array 1 + 1 + log(n) * 1 CSE 373 SP 18 - KASEY CHAMPION 16

  17. Building a Heap Insert has a runtime of (log(n)) If we want to insert a n items Building a tree takes O(nlog(n)) - Add a node, fix the heap, add a node, fix the heap Can we do better? - Add all nodes, fix heap all at once! CSE 373 SP 18 - KASEY CHAMPION 17

  18. Cleaver building a heap Floyds Method Facts of binary trees - Increasing the height by one level doubles the number of possible nodes - A complete binary tree has half of its nodes in the leaves - A new piece of data is much more likely to have to percolate down to the bottom than be the smallest element in heap 1. Dump all the new values into the bottom of the tree - Back of the array 2. Traverse the tree from bottom to top - Reverse order in the array 3. Percolate Down each level moving towards overall root CSE 373 SP 18 - KASEY CHAMPION 18

  19. Floyds buildHeap algorithm Build a tree with the values: 12, 5, 11, 3, 10, 2, 9, 4, 8, 15, 7, 6 12 1. 2. percolateDown(parent) starting at last index Add all values to back of array 5 11 10 2 9 3 1 7 6 4 8 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 15 12 5 11 3 10 2 9 4 8 7 6 CSE 373 SP 18 - KASEY CHAMPION 19

  20. Floyds buildHeap algorithm Build a tree with the values: 12, 5, 11, 3, 10, 2, 9, 4, 8, 1, 7, 6 12 2 2 5 3 3 1. 2. percolateDown(parent) starting at last index 1. percolateDown level 4 2. percolateDown level 3 3. percolateDown level 2 4. percolateDown level 1 Add all values to back of array 11 2 2 12 12 11 11 10 7 7 3 5 5 2 9 15 7 10 10 6 4 8 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 12 5 11 3 10 2 9 4 8 7 6 15 CSE 373 SP 18 - KASEY CHAMPION 20

  21. Floyds Heap Runtime We step through each node n We call percolateDown() on each n log n thus it s O(nlogn) let s look closer Are we sure percolateDown() runs log n each time? - Half the nodes of the tree are leaves - Leaves run percolate down in constant time - the nodes have at most 1 level to travel - 1/8 the nodes have at most 2 levels to travel - etc work(n) n/2 * 1 + n/4 * 2 + n/8 * 3 + CSE 373 SP 18 - KASEY CHAMPION 21

  22. Closed form Floyds buildHeap work(n) ? 2 * 1 + ? 4 * 2 + ? 8* 3 + factor out n work(n) n(1 21 + 2 22 + 3 23+ ) find a pattern -> powers of 2 Summation! work(n) n(1 2 + 2 4 + 3 8+ ) ? ? ? = how many levels = height of tree = log(n) ???? ? ? 2? ?=1 Infinite geometric series logn? logn? ? 1 ??= ???? ? ? ???? ? ? 2? ? 2?= ? 2 ?? 1 < ? < 1 ? ?? 1 ?= ? 2? ?=1 ?=1 ?=0 ?=0 Floyd s buildHeap runs in O(n) time! CSE 373 SP 18 - KASEY CHAMPION 22

Related


No related presentations.

More Related Content