CompSci 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?0123456789106 10 7 1713 2592119610717139211925CompSci 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?61071713921192501 2 3 4 5 6 7 8 9106 10 7 1713 2592119CompSci 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 myListmyList.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);}136107179211925813610717921192501 2 3 4 5 6 7 8 9106 10 7 1713 2592119tvector 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 tenaciouslyenvisioned and set about tochange the world for womenand for technology. … shefought tirelessly for thedevelopment technology withpositive social and humanimpact.”ÿ “Anita Borg sought torevolutionize the world andthe way we think abouttechnology and its impact onour lives.”ÿ Founded Systers in 1987,http://www.iwt.org in
View Full Document
Unlocking...