19

When making a binary max heap, why is it better to implement it as a array based, and not a tree based (tree based as in, each node also having a pointer to it's parent)? In terms of run time analysis, memory usage, performance...

For binary max heap, the running times are:

  • insert: O(lg n)
  • delete min: O(lg n)
  • merge: O(n)

For a tree implementation

  • insert: O(lg n)
  • delete min: O(lg n)
  • merge: O(n)

Can anyone explain in detail?

6
  • 1
    The runtimes are wrong, where did you get them from? Heap is heap: the asymptotic runtimes are always the same. Feb 5, 2013 at 23:41
  • For insert run time, I got it from stackoverflow.com/questions/5609700/… (last post). So your saying there is no disadvantage in using linked lists compared to arrays?
    – omega
    Feb 5, 2013 at 23:44
  • No, I’m not saying that at all. You cannot implement a binary heap in a linked list while respecting the expected runtime characteristics. You understood the answer you linked to exactly the wrong way round. Feb 5, 2013 at 23:46
  • So if you implement it as a array or tree, the running time will be the same? And what about the memory usage, won't using tree version use up more memory?
    – omega
    Feb 5, 2013 at 23:50
  • 4
    The asymptotic running time will be the same – but the array has better cache locality and thus much better runtime in practice. And an explicit tree would use up more memory than an array. Feb 5, 2013 at 23:52

3 Answers 3

17

The tree uses more time and memory. The complexities are the same, but the constant factors are different.

The pointers of the tree use a lot of memory, compared to the array-based heap, where you barely need any additional space but the one taken by the values themselves. And manipulating these pointers takes time too. Allocating and deallocating nodes might take some time and space also...

In addition, there's no guarantee that the nodes of the tree will be together in memory. If any of the two alternatives takes benefit of the cache, it is the array-based heap.

10

With reference to what's been already said through others' answers, one may wonder why we don't use arrays for BST too. The binary heap has the requirement that it should be a complete binary tree. Therefore, the depth of the leaf nodes is always h or h-1. I believe it's this property that makes using arrays ideal for binary heaps and unfit for BST (since BST don't have the complete binary tree requirement - it could be strict/full/complete).

0

Tree vs Arrays:

Trees use more time and memory; even tho Asymptotically they have the same time-space complexity, the constant factors are different. Pointers require a lot more memory, especially if we have 3 pointers per node: for each node we would have:

  1. pointer to parent node
  2. pointer to left node
  3. pointer to right node

Allocating/ deallocating takes longer than just insert element in an array which have O(1) complexity.

technically using arrays or trees is asymptotically the same but in practice, trees are slower because they take more time and memory

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.