Deletion in min/max heaps
There's no need to bubble-up the element all the way to the root. You can replace the item to be removed with the last element in the heap. If that new element is less than its parent, then bubble it up. If it's greater than its children, bubble it down.

I implemented this in my DevSource article, A Priority Queue Implementation in C#. Full source is available at http://www.mischel.com/pubs/priqueue.zip.

See my Stack Overflow answer about this at https://stackoverflow.com/a/8706363/56778