heaps the efficiency of heapsort as we notedheapsort runs in ( *logntime although it may be slightly slower than quicksortan advantage over quicksort is that it is less sensitive to the initial distribution of data certain arrangements of key values can reduce quicksort to slow ( timewhereas heapsort runs in ( *logntime no matter how the data is distributed summary in an ascending-priority queue the item with the largest key is said to have the highest priority (it' the smallest item in descending queue priority queue is an abstract data type (adtthat offers methods for insertion of data and removal of the largest (or smallestitem heap is an efficient implementation of an adt priority queue heap offers removal of the largest itemand insertionin ( *logntime the largest item is always in the root heaps do not support ordered traversal of the datalocating an item with specific keyor deletion heap is usually implemented as an array representing complete binary tree the root is at index and the last item at index - each node has key less than its parents and greater than its children an item to be inserted is always placed in the first vacant cell of the array and then trickled up to its appropriate position when an item is removed from the rootit' replaced by the last item in the arraywhich is then trickled down to its appropriate position the trickle-up and trickle-down processes can be thought of as sequence of swapsbut are more efficiently implemented as sequence of copies the priority of an arbitrary item can be changed firstits key is changed thenif the key was increasedthe item is trickled upbut if the key was decreasedthe item is trickled down heap can be based on binary tree (not search treethat mirrors the heap structurethis is called treeheap algorithms exist to find the last occupied node or the first free node in treeheap heapsort is an efficient sorting procedure that requires ( *logntime