Delete an element from a heap runningtime heap delete    Posted: 5 years ago Edit answers (1) views (2697)

Write an algorithm to remove an arbitrary element from a heap of size $$N$$. What is the running time of the algorithm? Give an example.

 Posted: 5 years ago Updated: 5 years ago 0 0 Edit For Max-heap, Move the last element $$x$$ of the heap in place of the item to be deleted. If $$x$$ is less than its parent and greater than its children we are done. If $$x$$ is greater than its parents perform up-heap operation. If $$x$$ is less than one or both of its children perform down-heap operation. Time complexity of the algorithm is $$O(logN)$$. Example - Priority queue of scheduled jobs and somebody cancels one of the jobs.