Creating HeapsArray-based heapThinking about heapsAdding values to heapAdding values, details (pseudocode)Removing minimal elementAnita Borg 1949-2003CompSci 100E25.1Creating HeapsHeap 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 arrayHeap is a binary tree with shape property, heap/value propertyshape: 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 heapstore “node values” in array beginning at index 1for node with index kleft child: index 2*kright child: index 2*k+1why 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 heapsWhere 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 heapto maintain heap shape, must add new value in left-to-right order of last levelcould violate heap propertymove value “up” if too smallchange places with parent if heap property violatedstop when parent is smallerstop when root is reachedpull 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 elementWhere is minimal element?If we remove it, what changes, shape/property?How can we maintain shape?“last” element moves to rootWhat 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