Delete an element from a heap
  • Posted: 5 years ago
  • Edit
  • answers (1)
  • views (2663)

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 Answers

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.

You need to Sign In to post your solution.