DOC PREVIEW
Duke CPS 100E - Creating Heaps

This preview shows page 1-2 out of 7 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 7 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 7 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 7 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Creating HeapsArray-based heapThinking about heapsAdding values to heapAdding values, details (pseudocode)Removing minimal elementAnita Borg 1949-2003CompSci 100E25.1Creating HeapsHeap is an array-based implementation of a binary tree used for implementing priority queues, supports:insert, findmin, deletemin: complexities?Using array minimizes storage (no explicit pointers), faster too --- children are located by index/position in arrayHeap is a binary tree with shape property, heap/value propertyshape: tree filled at all levels (except perhaps last) and filled left-to-right (complete binary tree)each node has value smaller than both childrenCompSci 100E25.2Array-based heapstore “node values” in array beginning at index 1for node with index kleft child: index 2*kright child: index 2*k+1why is this conducive for maintaining heap shape?what about heap property?is the heap a search tree?where is minimal node?where are nodes added? deleted?0 1 2 3 4 5 6 7 8 9 106 10 7 17 13 259 21 19610717139211925CompSci 100E25.3Thinking about heapsWhere is minimal element?Root, why?Where is maximal element?Leaves, why?How many leaves are there in an N-node heap (big-Oh)? O(n), but exact?What is complexity of find max in a minheap? Why?  O(n), but ½ N?Where is second smallest element? Why? Near root?6107171392119250 1 2 3 4 5 6 7 8 9 106 10 7 17 13 259 21 19CompSci 100E25.4Adding values to heapto maintain heap shape, must add new value in left-to-right order of last levelcould violate heap propertymove value “up” if too smallchange places with parent if heap property violatedstop when parent is smallerstop when root is reachedpull parent down, swapping isn’t necessary (optimization)13610717921192581361071792119256107179211925138insert 8bubble 8 up6717921192581310CompSci 100E25.5Adding values, details (pseudocode)void add(Object elt){ // add elt to heap in myList myList.add(elt); int loc = myList.size()-1; while (1 < loc && elt < myList[loc/2]) { myList[loc] = myList[loc/2]; loc = loc/2; // go to parent } // what’s true here? myList.set(loc,elt);}13610717921192581361071792119250 1 2 3 4 5 6 7 8 9 106 10 7 17 13 259 21 19ArrayList myListCompSci 100E25.6Removing minimal elementWhere is minimal element?If we remove it, what changes, shape/property?How can we maintain shape?“last” element moves to rootWhat property is violated?After moving last element, subtrees of root are heaps, why?Move root down (pull child up) does it matter where?When can we stop “re-heaping”?Less than both children Reach a leaf 136107179211925132510717921191371025179211913710917252119CompSci 100E25.7Anita Borg 1949-2003“Dr. Anita Borg tenaciously envisioned and set about to change the world for women and for technology. … she fought tirelessly for the development technology with positive social and human impact.”“Anita Borg sought to revolutionize the world and the way we think about technology and its impact on our lives.”Founded Systers in 1987, http://www.iwt.org in


View Full Document

Duke CPS 100E - Creating Heaps

Documents in this Course
Topics

Topics

9 pages

Lecture

Lecture

3 pages

Notes

Notes

2 pages

Hashing

Hashing

19 pages

Lecture

Lecture

59 pages

Lecture

Lecture

6 pages

Lecture

Lecture

4 pages

Lecture

Lecture

20 pages

Lecture

Lecture

12 pages

Lecture

Lecture

12 pages

Lecture

Lecture

7 pages

Lecture

Lecture

8 pages

Lecture

Lecture

10 pages

Lecture

Lecture

4 pages

Notes

Notes

16 pages

Lecture

Lecture

5 pages

Lecture

Lecture

9 pages

Lecture

Lecture

4 pages

Lecture

Lecture

13 pages

Lecture

Lecture

6 pages

Lecture

Lecture

16 pages

Lecture

Lecture

5 pages

Lecture

Lecture

5 pages

Lecture

Lecture

12 pages

Lecture

Lecture

12 pages

Lecture

Lecture

10 pages

Sets

Sets

14 pages

Lecture

Lecture

9 pages

Lecture

Lecture

4 pages

Test 1

Test 1

7 pages

Load more
Download Creating Heaps
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 Creating Heaps 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 Creating Heaps 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?