2

is there a way to convert a min heap to a BST in O(n) complexity? I'm just interested in knowing if it's even possible, not exactly how it's done. there's a question here on SO about max heap, but the answers were just too confusing for me.

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
littlerunaway
  • 443
  • 2
  • 8
  • 18
  • If you have the items in order, you can create a binary tree in O(n) time. So it depends on whether you can extract all the items (in order) from the min heap in O(n) time. IIRC for a binary heap it takes O(n log n) time, but the binary heap isn't the only heap/priority queue data structure. I seem to remember there being a heap that supports amortized O(1) extractions, which should mean you get O(n) total for extracting everything - I forget which one. If I'm right, yes, you can convert from that specific min heap data structure to a binary tree in O(n) time. –  Jun 18 '14 at 17:11
  • I'm talking about a binary heap. but suppose I wasn't, if extracting 1 element takes amortized O(1), then O(n) in total will be average (or amortized, or whatever you call it, I always confuse those), won't it? and I need O(n) in worse case – littlerunaway Jun 18 '14 at 17:23
  • Amortized O(1) is sort-of constant-on-average, but that's a pretty vague intuition for a more formal thing. When you do n operations with amortized O(1) complexity, you end up with *genuine* (not amortized) O(n). The way I remember one argument is basically budgeting so you never go overdrawn. In this case you'd budget some constant amount of work per operation and, though the actual cost per operation varies, you prove you can never go overdrawn. Thus for the full sequence of n operations you cannot have total costs more than n times the O(1) you budgeted for - a genuine O(n) complexity. –  Jun 18 '14 at 20:26
  • BTW - the heap data structure I was thinking of is [the Fibonacci heap](https://en.wikipedia.org/wiki/Fibonacci_heap). Unfortunately, it turns out the `delete-min` operation is O(log n) amortized time, so you can't get the O(n) performance - only O(n log n) which you could get from a binary heap anyway. Some other operations are amortized O(1) time, but you'd need `delete-min` to remove each `min`. –  Jun 18 '14 at 20:36
  • so I understand that O(n) is not possible. how do I explain that? can I say that for a BST I need a sorted array and to get it from a binary heap I need a comparison based sorting which can't be less than O(nlogn)? – littlerunaway Jun 18 '14 at 21:20
  • possible duplicate of [Converting a heap to a BST in O(n) time?](http://stackoverflow.com/questions/14106821/converting-a-heap-to-a-bst-in-on-time) – templatetypedef Jun 18 '14 at 23:11
  • oh, this one didn't come up in my search. that definitely answers my questoin, thanx – littlerunaway Jun 19 '14 at 04:13
  • @littlerunaway - you don't necessarily need a sorted array, but you do need to be able to get the items in sorted order. A binary heap provides that, but each item costs O(log n), so getting all n of them is O(n log n). If you're thinking of the binary heap being stored in an array, and sorting it to get the items in order, consider that the [heap sort](https://en.wikipedia.org/wiki/Heapsort) algorithm sorts an array by (1) heapifying, then (2) repeatedly extracting the next item in order from the heap and placing it in the space in the array freed by that heap extraction. –  Jun 19 '14 at 19:05
  • There's a proof that you can't sort a sequence of items (using only relative operators and item moves) in better than O(n log n) time. When I thought there might be a way to convert a heap to a BST in O(n) time it was because a heap is already structured based on ordering. With a binary heap that's not good enough, but I thought there might be an alternative heap where it was good enough. Sadly it looks like no. Anyway, given that a heapify is O(n), if you could extract all items from a binary heap in order in O(n) time you could sort the array in O(n) time which is impossible. –  Jun 19 '14 at 19:13

0 Answers0