Quadtrees .edu
[Pages:28]L11: Quadtrees
CSE373, Winter 2020
Quadtrees
CSE 373 Winter 2020
Instructor: Hannah C. Tang
Teaching Assistants:
Aaron Johnston Ethan Knutson
Amanda Park
Farrell Fileas
Anish Velagapudi Howard Xiao
Brian Chan
Jade Watkins
Elena Spasova
Lea Quan
Nathan Lipiarski Sam Long Yifan Bai Yuma Tou
Announcements
L11: Quadtrees
CSE373, Winter 2020
Homework 4: Heap is released and due Wednesday
Hint: you will need an additional data structure to improve the
runtime for changePriority(). It does not affect the correctness of your PQ at all. Please use a built-in Java collection instead of implementing your own.
Hint: If you implemented a unittest that tested the exact thing the
autograder described, you could run the autograder's test in the debugger (and also not have to use your tokens).
Please look at posted QuickCheck; we had a few corrections!
2
Lecture Outline
L11: Quadtrees
CSE373, Winter 2020
Heaps, cont.: Floyd's buildHeap
Review: Set/Map data structures and logarithmic runtimes
Multi-dimensional Data
Uniform and Recursive Partitioning
Quadtrees
3
L11: Quadtrees
Other Priority Queue Operations
CSE373, Winter 2020
The two "primary" PQ operations are: removeMax() add()
However, because PQs are used in so many algorithms there are three common-but-nonstandard operations: merge(): merge two PQs into a single PQ buildHeap(): reorder the elements of an array so that its contents can
be interpreted as a valid binary heap
changePriority(): change the priority of an item already in the heap
4
L11: Quadtrees
buildHeap: Na?ve Implementation
CSE373, Winter 2020
buildHeap() takes an array of size N and applies the heapordering principle to it
Na?ve implementation: Start with an empty array (representing an empty binary heap) Call add() N times Runtime: ??
Can we do better?
5
L11: Quadtrees
buildHeap: Clever Implementation
CSE373, Winter 2020
~? of all nodes in a complete binary tree are leaves
Remember that 20 + 21 + ... 2n 20: 1
= 2n+1 ? 1
21: 2
Clever implementation:
Start with full array
22: 4
(representing a binary heap
with lots of violations)
23: 8
Call percolateDown() N/2
times
Runtime: ??
This "clever implementation" is called Floyd's Algorithm
6
L11: Quadtrees
What is buildHeap()'s runtime? Start with full array
(representing a binary heap 20: 1 with lots of violations)
Call percolateDown() N/2 times 21: 2
A. (1)
22: 4
B. (log N)
C. (N)
23: 8
D. (N log N)
E. I'm not sure ...
CSE373, Winter 2020
uwcse373
7
Lecture Outline
L11: Quadtrees
CSE373, Winter 2020
Heaps, cont.: Floyd's buildHeap
Review: Set/Map data structures and logarithmic runtimes
Multi-dimensional Data
Uniform and Recursive Partitioning
Quad-Trees
8
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
- extended abstract mit
- sap business one 9
- standard time zones of the world october 2015
- project stakeholder management a case study of a
- k007en steel sheet piles
- 2021 apple supplier list
- the strengths and weaknesses of the brazilian internet
- hurricane electric network map he
- a study on business model adopted by uber to disrupt the
- quadtrees edu