the heap arraya new array can be createdand the data from the old array copied into it (unlike the situation with hash tableschanging the size of heap doesn' require reordering the data the copying operation takes linear timebut enlarging the array size shouldn' be necessary very oftenespecially if the array size is increased substantially each time it' expanded (by doubling itfor examplein javaa vector class object could be used instead of an arrayvectors can be expanded dynamically efficiency of heap operations for heap with substantial number of itemsit' the trickle-up and trickle-down algorithms that are the most time-consuming parts of the operations we've seen these algorithms spend time in looprepeatedly moving nodes up or down along path the number of copies necessary is bounded by the height of the heapif there are five levelsfour copies will carry the "holefrom the top to the bottom (we'll ignore the two moves used to transfer the end node to and from temporary storagethey're always necessary so they require constant time the trickleup(method has only one major operation in its loopcomparing the key of the new node with the node at the current location the trickledown(method needs two comparisonsone to find the largest childand second to compare this child with the "lastnode they must both copy node from top to bottom or bottom to top to complete the operation heap is special kind of binary treeand as we saw in the number of levels in binary tree equals log ( + )where is the number of nodes the trickleup(and trickledown(routines cycle through their loops - timesso the first takes time proportional to log nand the second somewhat more because of the extra comparison thus the heap operations we've talked about here all operate in (logntime heapsort the efficiency of the heap data structure lends itself to surprisingly simple and very efficient sorting algorithm called heapsort the basic idea is to insert the unordered items into heap using the normal insert(routine repeated application of the remove(routine will then remove the items in sorted order here' how that might lookfor( = <sizej++theheap insertanarray[ )for( = <sizej++anarray[jtheheap remove()/from unsorted array /to sorted array because insert(and remove(operate in (logntimeand each must be applied timesthe entire sort requires ( *logntimewhich is the same as quicksort howeverit' not quite as fast as quicksort partly this is because there are more operations in the inner while loop in trickledown(than in the inner loop in quicksort howeverseveral tricks can make heapsort more efficient the first saves timeand the second saves memory trickling down in place