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 arrayand 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 first its key is changedthenif the key was increasedthe item is trickled upwhile if the key was decreased the item is trickled down heapsort is an efficient sorting procedure that requires ( *logntime conceptually heapsort consists of making insertions into heapfollowed by removals heapsort can be made to run faster by applying the trickle-down algorithm directly to / items in the unsorted arrayrather than inserting items the same array can be used for the initial unordered datafor the heap arrayand for the final sorted data thus heapsort requires no extra memory