Floyd's Algorithm for Heap Analysis

This content covers topics related to Floyd's algorithm, properties of heaps, completeness, and array implementation. It includes visual reviews on identifying heaps, array properties, heap operations, and runtimes. The material also discusses heap operations like inserting, deleting minimum items, and changing priorities. Check out the detailed images and descriptions for a comprehensive understanding.

• Algorithm Analysis
• Heap properties
• Heap operations
• Array implementation
• Floyds algorithm

beniahc Follow

Uploaded on Mar 10, 2025 | 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.

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.

Presentation Transcript

1. CSE 373 APRIL 7TH FLOYD S ALGORITHM

2. ASSORTED MINUTIAE HW1P2 due tonight HW2 out No java libraries

3. TODAYS SCHEDULE buildHeap() Floyd s algorithm Analysis

4. REVIEW Heaps Properties Completeness Heap property

5. REVIEW Is this a heap? 10 20 80 30 15

6. REVIEW Is this a heap? No. Why? 10 20 80 30 15

7. REVIEW Is this a heap? 1 50 3 450 75 60 8 10 10

8. REVIEW Is this a heap? No. Why 1 50 3 450 75 60 8 10 10

9. REVIEW Is this a heap? 10 20 80 40 60 85 99 50 700

10. REVIEW Heaps Properties Completeness Heap property Implementation Array (0 v 1 indexing)

11. REVIEW Array property A B C F G D E H I J K L

12. REVIEW Array property 1 A 2 3 B C 6 7 4 5 F G D 9 E 11 8 10 12 H I J K L

13. REVIEW Array property 1 A 2 3 B C 6 7 4 5 F G D 9 E 11 8 10 12 H I J K L A 1 B 2 C 3 D 4 E 5 F 6 G 7 H 8 I 9 J 10 K 11 L 12 0 13

14. REVIEW Array property 0 indexing: left = 2*i+1 right: 2*i+2 parent: (i-1)/2 1 indexing: left = 2*i right = 2*i +1 parent: i/2

15. HEAPS Operations Insert: adds a data, priority pair into the heap

16. HEAPS Operations Insert: adds a data, priority pair into the heap deleteMin: returns and removes the item of smallest priority from the heap changePriority: changes the priority of a particular item in the heap What are the (worst-case) runtimes for these operations?

17. HEAPS Insert: Add the element at the bottom of the tree Percolate up that element to its correct place Adding to the end of a tree? O(1) Percolating up? O(height) O(log n) What is the height of a heap? log2 n

18. HEAPS deleteMin: Move the last element up to the top of the tree Percolate that element down Return the original root of the tree. Copying element? O(1) Percolating down? O(log n) Returning element? O(1)

19. HEAPS changePriority: Find the element Percolate up/down Finding in a heap? O(n) Why? Heap property does not give us the divide and conquer benefit Percolate up/down? O(log n) On average, is it faster to percolate up or down?

20. HEAPS Facts of binary trees Increasing the height by one doubles the number of possible nodes Therefore, 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 item in the heap

21. BUILDHEAP Back to the problem from Wednesday Given an arbitrary array of size n, form the array into a heap Na ve approach(es): Sort the array: O(n log n) Insert each element into a new heap. log n operation performed n times: O(n log n)

22. FUN FACTS! Is it really O(n log n)? Early insertions are into empty trees O(1)! Consider a simpler example, creating a sorted linked list. Adding at the end of a linked list with k items takes O(k) operations. 1+2+3+4+5 What is this summation?

23. FUN FACTS! What does this mean? Summing k from 1 to n is still O(n2) Similarly, summing log(k) from 1 to n is O(n log n)

24. BUILDHEAP So a na ve buildheap takes O(n log n) Why implement at all? If we can get it O(n)!

25. FLOYDS METHOD Traverse the tree from bottom to top Reverse order in the array Start with the last node that has children. How to find? Size / 2 Percolate down each node as necessary Wait! Percolate down is O(log n)! This is an O(n log n) approach!

26. FLOYDS METHOD It is O(n log n), because big O is an upper bound, but there is a tighter analysis possible! How far does each node travel (at worst) 1/2 of the nodes don t move: These are leaves Height = 0 1/4 can move at most one 1/8 can move at most two

27. FLOYDS METHOD Thanks Wolfram Alpha! Does this look like an easier summation?

28. FLOYDS METHOD This is a must know summation! 1/2 + 1/4 + 1/8 + = 1 How do we use this to prove our complicated summation?

29. FLOYDS METHOD + 1/2n = 1 1/2 + 1/4 + 1/8 + 1/2n = 1/2 1/4 + 1/8 + 1/2n = 1/4 1/8 Vertical columns sum to: i/2^i, which is what we want What is the right summation? Our original summation plus 1

30. FLOYDS METHOD This means that the number of swaps we perform in Floyd s method is 2 times the size So Floyd s method is O(n)

31. NEXT WEEK Guest lecturer! Proof of Floyd s method correctness Introducing the Dictionary ADT