Deleting a random element from a heap

Question

I read a few articles which said that, in a heap, only the root element can be deleted. However, why can't we delete elements, using the below approach? - Find the index of the key element you want to delete - Swap this element with the last element, so the key becomes the last element - Re-heapify starting at the original index of the key(which you have now swapped with the last element) - Reduce size of heap by 1 So, the code would look like ``` static void delete(int[] a, int key) { int i = 0; for(i = 0;i a[i]) next = left; if(right <= limit && a[right] > a[next] ) next = right; if(next!=i) { swap(a, next, i); max_heapify_forheapsort(a, next, limit); } } ```

Accepted Answer

It's certainly possible to delete elements from a heap with sift-up or sift-down operations as you propose. (It's similarly possible to change the key of any item in the heap and use sift-up or -down operations to restore the heap property.)

The tricky bit is what you stated quickly at the outset: "Find the index." A naive implementation requires O(n) to do this, and that kills heap efficiency. What people mean when they say "you can't delete" is that with a naive implementation you can't delete efficiently.

Fortunately it's not hard to make finding the index O(1). Just maintain a "reverse map" in parallel with the heap array, e.g. a hash map from objects to heap array indices. It's easy to update this map without adding asymptotic complexity to any of the heap operations, and with it - as you point out - delete has complexity O(log n). The sift up/down dominates the map lookup to find the index.

If you're interested in a tested implementation, here's one where the heap contains indices into another array of objects. Therefore the reverse map is implemented as an array `q->locs[k]`, which is the index of the heap element that contains `k` (which is an index into the object table).

Many problems in computer science can be solved by adding a level of indirection!

Edit

Since OP asked about why a sift up might be required to delete, consider the min heap

```
          1
    20          2 
 30    40    3     4
```

We want to delete 30, so move 4 (the last array element) into its position:

```
          1
    20          2 
 4     40    3 
```

Clearly a sift up is required.

Deleting a random element from a heap

Solution

Problem