0

I have this problem - i'm keeping a data structure that contains two different heaps , a minimum heap and a maximum heap that does not contain the same data.

My goal is to keep some kind of record for each node location in either of the heaps and have it updated with the heaps action. Bottom line - i'm trying to figure out how can i have a delete(p) function that works in lg(n) complexity. p being a pointer data object that can hold any data.

Thanks, Ned.

Ned
  • 355
  • 2
  • 9
  • 24

1 Answers1

1

If your heap is implemented as an array of items (references, say), then you can easily locate an arbitrary item in the heap in O(n) time. And once you know where the item is in the heap, you can delete it in O(log n) time. So find and remove is O(n + log n).

You can achieve O(log n) for removal if you pair the heap with a dictionary or hash map, as I describe in this answer.

Deleting an arbitrary item in O(log n) time is explained here.

The trick to the dictionary approach is that the dictionary contains a key (the item key) and a value that is the node's position in the heap. Whenever you move a node in the heap, you update that value in the dictionary. Insertion and removal are slightly slower in this case, because they require making up to log(n) dictionary updates. But those updates are O(1), so it's not hugely expensive.

Or, if your heap is implemented as a binary tree (with pointers, rather than the implicit structure in an array), then you can store a pointer to the node in the dictionary and not have to update it when you insert or remove from the heap.

That being said, the actual performance of add and delete min (or delete max for the max heap) in the paired data structure will be lower than with a standard heap that's implemented as an array, unless you're doing a lot of arbitrary deletes. If you're only deleting an arbitrary item every once in a while, especially if your heap is rather small, you're probably better off with the O(n) delete performance. It's simpler to implement and when n is small there's little real difference between O(n) and O(log n).

Community
  • 1
  • 1
Jim Mischel
  • 131,090
  • 20
  • 188
  • 351
  • 2
    `"... when n is small there's little real difference between O(n) and O(log n)"` - careful with statements like that. People may not know what "small" is and may even miss "when n is small" altogether. – Bernhard Barker Mar 13 '13 at 21:48
  • True enough. Good observation. Definitely not something I'd say to a group of beginning programmers. "Small" is definitely a subjective thing. To some people, 100 is small. To others, 1,000 or 1,000,000. But then, so is "every once in a while". And if somebody misses "when n is small," ... hey, that's *their* problem! – Jim Mischel Mar 13 '13 at 22:42