next job selected is the one with the highest priority priority is indicated by particular value associated with the job (and might change while the job remains in the wait listwhen collection of objects is organized by importance or prioritywe call this priority queue normal queue data structure will not implement priority queue efficiently because search for the element with highest priority will take th(ntime listwhether sorted or notwill also require th(ntime for either insertion or removal bst that organizes records by priority could be usedwith the total of inserts and remove operations requiring th( log ntime in the average case howeverthere is always the possibility that the bst will become unbalancedleading to bad performance insteadwe would like to find data structure that is guaranteed to have good performance for this special application this section presents the heap data structure heap is defined by two properties firstit is complete binary treeso heaps are nearly always implemented using the array representation for complete binary trees presented in section secondthe values stored in heap are partially ordered this means that there is relationship between the value stored at any node and the values of its children there are two variants of the heapdepending on the definition of this relationship max-heap has the property that every node stores value that is greater than or equal to the value of either of its children because the root has value greater than or equal to its childrenwhich in turn have values greater than or equal to their childrenthe root stores the maximum of all values in the tree min-heap has the property that every node stores value that is less than or equal to that of its children because the root has value less than or equal to its childrenwhich in turn have values less than or equal to their childrenthe root stores the minimum of all values in the tree note that there is no necessary relationship between the value of node and that of its sibling in either the min-heap or the max-heap for exampleit is possible that the values for all nodes in the left subtree of the root are greater than the values for every node of the right subtree we can contrast bsts and heaps by the strength of their ordering relationships bst defines total order on its nodes in thatgiven the positions for any two nodes in the treethe one to the "left(equivalentlythe one appearing earlier in an inorder traversalhas smaller key value than the one to the "right in contrasta heap implements partial order given their positionswe can determine the relative order for the key values of two nodes in the heap only if one is descendant of the other the term "heapis also sometimes used to refer to memory pool see section