11

I was wondering if we can use a binary search tree to simulate heap operations (insert, find minimum, delete minimum), i.e., use a BST for doing the same job?

Are there any kind of benefits for doing so?

Junaid
  • 1,668
  • 7
  • 30
  • 51
  • 2
    Why would you want to do that? It'll be slower and bigger than the standard array-and-implicit-links approach. – harold Oct 24 '11 at 16:26
  • @harold this can potentially be better in term of performance than the traditional heap data structure. Moreover it is more flexible to perform the operation in which BST can do but not Heap. – Yeo Nov 22 '14 at 06:14
  • 1
    @Yeo my experience tells me otherwise, so I'm not going to believe such a claim until it is substantiated. BSTs are more flexible though, but that doesn't help if, as OP said, you want to use it for doing the same job as a heap. – harold Nov 22 '14 at 08:42

4 Answers4

8

Sure we can. but with a balanced BST.

The minimum is the leftest element. The maximum is the rightest element. finding those elements is O(logn) each, and can be cached on each insert/delete, after the data structure was modified [note there is room for optimizations here, but this naive approach also doesn't contradict complexity requirement!]

This way you get insert,delete: O(logn), findMin/findMax: O(1)

EDIT:
The only advantage I can think of in this implementtion is that you get both findMin,findMax in one data structure.
However, this solution will be much slower [more ops per step, more cache misses are expected...] and consume more space then the regular array-based implementation of a heap.

amit
  • 175,853
  • 27
  • 231
  • 333
  • 1
    See [Min-max heap](http://en.wikipedia.org/wiki/Min-max_heap) for an array-based heap implementation that gives you O(1) `findMin` and `findMax`, and O(log n) `insert`, `deleteMin`, and `deleteMax`. The only real benefit I see to the BST implementation is that you could find an arbitrary element in O(log n). That could come in handy if you wanted the ability to delete an arbitrary node. With the array-based implementation, finding the node is O(n). – Jim Mischel Nov 22 '14 at 06:34
  • 1
    This has one major downside: you lose the average O(1) insert of heaps, which is basically the only reason to use them: http://stackoverflow.com/a/29548834/895245 – Ciro Santilli OurBigBook.com Jun 20 '15 at 05:33
4

Yes, but you lose the O(1) average insert of the heap

As others mentioned, you can use a BST to simulate a heap.

However this has one major downside: you lose the O(1) insert average time, which is basically the only reason to use the heap in the first place: https://stackoverflow.com/a/29548834/895245

If you want to track both min and max on a heap, I recommend that you do it with two heaps instead of a BST to keep the O(1) insert advantage.

Community
  • 1
  • 1
Ciro Santilli OurBigBook.com
  • 347,512
  • 102
  • 1,199
  • 985
0

Basically, I agree with @amit answer. I will elaborate more on the implementation of this modified BST.

Heap can do findMin or findMax in O(1) but not both in the same data structure. With a slight modification, the BST can do both findMin and findMax in O(1).

In this modified BST, you keep track of the the min node and max node every time you do an operation that can potentially modify the data structure. For example in insert operation you can check if the min value is larger than the newly inserted value, then assign the min value to the newly added node. The same technique can be applied on the max value. Hence, this BST contain these information which you can retrieve them in O(1). (same as binary heap)

In this BST (specifically Balanced BST), when you pop min or pop max, the next min value to be assigned is the successor of the min node, whereas the next max value to be assigned is the predecessor of the max node. Thus it perform in O(1). Thanks to @JimMischel comment below however we need to re-balance the tree, thus it will still run O(log n). (same as binary heap)

In my opinion, generally Heap can be replaced by Balanced BST because BST perform better in almost all of the heap data structure can do. However, I am not sure if Heap should be considered as an obsolete data structure. (What do you think?)

PS: Have to cross reference to different questions: https://stackoverflow.com/a/27074221/764592

Community
  • 1
  • 1
Yeo
  • 11,416
  • 6
  • 63
  • 90
  • Actually, a [min-max heap](http://en.wikipedia.org/wiki/Min-max_heap) implemented in an array can do `findMin` *and* `findMax` in O(1). All other operations: `insert`, `deleteMin`, and `deleteMax` are O(log n). Also, if you continually `deleteMin` as you describe, your tree will become unbalanced. Finally, your last statement is probably false. I've yet to see a BST implementation of a heap that can outperform an array implementation. Maintaining a balanced binary tree is much more expensive than maintaining a heap in an array. – Jim Mischel Nov 22 '14 at 06:32
  • Thanks @JimMischel, I haven't take a look at min-max heap. But it's good for me to know this. and thanks for noticing the flaw. Thus we need to re-balance the tree which perform O(log n) for `deleteMin` or `deleteMax` which is the same complexity as binary heap. – Yeo Nov 22 '14 at 07:27
  • Heap is *not* obsolete because of O(1) average insert which is its raison d'etre. Implementing it with BST loses that: http://stackoverflow.com/a/29548834/895245 – Ciro Santilli OurBigBook.com Jun 20 '15 at 05:32
0

Yes, we can, by simply inserting and finding the minimum into the BST. There are few benefits, however, since a lookup will take O(log n) time and other functions receive similar penalties due to the stricter ordering enforced throughout the tree.

thiton
  • 35,651
  • 4
  • 70
  • 100
  • You don't have to do a lookup. You just have to keep track the lowest and the highest value in your data structure. All can be perform in O(1). – Yeo Nov 22 '14 at 06:17