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 commentsSecurity 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
Unlocking...