Course contentsShow
← Computer Science
Lesson 595 of 2,87214. Heaps and Priority QueuesFree lesson

Delete Arbitrary Element

Removing non-root elements by replacing with last element and bidirectional bubbling.

Delete Arbitrary Element

What you'll learn: How to remove any element from a heap (not just the root) while maintaining heap structure and order properties.

The Challenge

You've learned how to extract the min/max element (the root), but what if you need to delete an element buried somewhere in the middle of your heap? You can't just remove it—that would violate the complete binary tree structure!

The Two-Step Solution

Deleting an arbitrary element combines techniques you already know:

Step 1: Replace with Last Element Just like in extract operations, swap the target element with the very last element in the heap (the rightmost leaf on the bottom level). Then remove that last position. This preserves the complete binary tree shape.

Step 2: Bidirectional Bubbling Here's the twist: unlike insert (bubble up only) or extract (bubble down only), you might need to bubble in either direction:

  • If the replacement value is smaller than its parent (min-heap), bubble up
  • If the replacement value is larger than its children (min-heap), bubble down
  • Sometimes the replacement happens to be in the perfect spot already!

Analogy

Imagine a corporate hierarchy pyramid. You need to remove a middle manager. You grab the most junior person from the bottom-right corner and place them in that vacant spot. Now: are they too junior? Move them down. Overqualified? Move them up. Exactly right? Done!

Implementation Note

You'll typically check both conditions: attempt to bubble up first, and if no swap occurred, attempt to bubble down. Only one direction will actually move the element (or neither).

Key Takeaway: Deleting an arbitrary heap element requires replacing it with the last element, then restoring heap order by bubbling bidirectionally—up if too small, down if too large.