New version page

TRINITY CSCI 1321 - Heap Based Priority Queues

Documents in this Course
Recursion

Recursion

11 pages

Iterators

Iterators

10 pages

Actors

Actors

9 pages

Recursion

Recursion

15 pages

Recursion

Recursion

10 pages

Threads

Threads

7 pages

Trees

Trees

11 pages

Load more
Upgrade to remove ads
Upgrade to remove ads
Unformatted text preview:

Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 81Heap Based Priority Queues4-22-20102Opening Discussion■Do you have any questions about the quiz?■Solutions to the interclass problem.■Do you have any questions about the assignment?■Minute essay commentsSecurity with sockets?Examples of when to use UDP.Dealing with firewalls.Is it a problem if sockets are used at the same time?Does the server stay open forever?What happens if the message doesn't get through?Changing the class examples to a different program?3Heaps■When you implemented the priority queue for your game, you used a sorted linked list. This data structure has the disadvantage that adding takes O(n) time. For data structures we try to avoid O(n) if at all possible for the common operations because it typically leads to O(n2) overall performance.■There is another data structure we can use to implement that priority queue called a heap. Using a heap, none of the operations will be worse than O(log n).■There are actually many types of heaps. We will be doing the simplest type, the binary heap.4Binary Heaps as Trees■You can view a binary heap as a type of binary tree, though our final implementation will not actually use a binary tree.■Binary heaps are complete trees that have heap ordering.A complete tree is one that only starts filling the next row after the one above it is completely full. We will fill rows from left to right adding in new nodes until we have to move down to the next row.Heap ordering is simply the property that each node has a higher priority than its children. So in your game each node would have an entity with a lower update time than the children.5Adding and Removing■When we add to a binary heap we simply place the new element at the next free spot on the tree. We then have to shift things to restore heap ordering. We refer to the new node as a bubble which moves up through the tree until it comes to rest.■The only item we can remove from the tree is the root, which has the highest priority thanks to the heap ordering. To keep the heap complete we move the last element up to the root and let it sink down through the tree until it comes to rest.■Both of these operations are always O(log n) because the heap is complete.6Heaps as Arrays■The tree structure is nice for visualizing the heap, but it is extremely inefficient for implementation.■If we order the nodes starting at 1 you will see nice mathematical relationships between parents and children. We use this numbering as an index into a array and store the heap in an array or an array based list.7Code■I'm not going to write a heap for you because that is your main task in assignment 7. Instead I would like to fill in some of the holes in our drawing program.■If we can get add to use the tree structure properly then perhaps we can make transforms that use our formula class and get the slider to adjust a variable for the formula.8Minute Essay■Why are the add and remove operations on a binary heap always O(log n) when a normal binary tree can't promise that?■Interclass Problem – Add commands to the drawing project for “connect” and “chat” that can connect to another drawing program and send chat


View Full Document
Download Heap Based Priority Queues
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Heap Based Priority Queues and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Heap Based Priority Queues 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?