DOC PREVIEW
TRINITY CSCI 1321 - Heaps and Binary Tree Implementation

This preview shows page 1-2-3 out of 9 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Heaps and Binary Tree Implementation4-15-2004Opening DiscussionWhat did we talk about last class?Do you have any questions about the assignment?We want a faster way to do a priority queue. How might we do this? We have used a list, would a tree work?CodeLet’s look code to implement a sorted binary tree.HeapsThe only implementation we have for a priority queue right now is to use a sorted linked list. However, the O(n) adds make that inefficient when n gets really large.A heap is a data structure like a binary tree that can be used for an efficient priority queue.Instead of using the ordering of a sorted tree, it uses “heap ordering”, heap trees also have to be complete.Heap Order and Complete TreesInstead of putting lesser things to the left, in a heap, the children of a node all have a “lower priority” than that node. In your game, lower priority means a larger update time.A complete tree is a tree that is filled from left to right and each level is completely filled before it starts putting anything in the next level.Complete Trees as ArraysWhen a tree is complete we can easily represent it as an array. In a complete tree, the left most nodes in a generation get their children first, and nodes get a left child before a right child.Note that for a binary tree, the path to a leaf can be expressed as a binary number. If we prefix it with a 1 we get a unique encoding where the first element is 1. This also allows us to quickly find parents.Inserting to a HeapTo insert into a binary heap, we put a “bubble” node at the next open space and let it move up the heap until it moves into place.At each step it gets swapped with a higher priority object, so the heap-order property is maintained.This operation always takes O(log n) time because the heap is a complete tree.Removing from a HeapTo remove the smallest element we simply make the “bubble” node at the top and this time the last element in the heap is what will wind up filling it. We let it “sink” down through the tree. At each step we swap it with the smaller of the two children assuming that it is larger than them. If it isn’t it can stop there.Minute EssayDo you have any questions about the heap? Show me what your heap would look like if you added 5,3,7,1,6 then pulled off two elements. Draw a total of 6 tree structures to show it.The semester is winding down and we are talking about more diverse topics. Read up on java.io for next


View Full Document

TRINITY CSCI 1321 - Heaps and Binary Tree Implementation

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
Download Heaps and Binary Tree Implementation
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 Heaps and Binary Tree Implementation 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 Heaps and Binary Tree Implementation 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?