sec heaps and priority queues ( ( (cfigure the siftdown operation the subtrees of the root are assumed to be heaps (athe partially completed heap (bvalues and are swapped (cvalues and are swapped to form the final heap sum of total distances that elements can go is therefore log xn log = = - ( - from equation we know that this summation has closed-form solution of approximately so this algorithm takes th(ntime in the worst case this is far better than building the heap one element at timewhich would cost th( log nin the worst case it is also faster than the th( log naverage-case time and th( worst-case time required to build the bst removing the maximum (rootvalue from heap containing elements requires that we maintain the complete binary tree shapeand that the remaining node values conform to the heap property we can maintain the proper shape by moving the element in the last position in the heap (the current last element in the arrayto the root position we now consider the heap to be one element smaller unfortunatelythe new root value is probably not the maximum value in the new heap this problem is easily solved by using siftdown to reorder the heap because the heap is log levels deepthe cost of deleting the maximum element is th(log nin the average and worst cases the heap is natural implementation for the priority queues discussed at the beginning of this section jobs can be added to the heap (using their priority value as the ordering keywhen needed method removemax can be called whenever new job is to be executed some applications of priority queues require the ability to change the priority of an object already stored in the queue this might require that the object' position in the heap representation be updated unfortunatelya max-heap is not efficient