What are some differences between the two representations of a heap?


#1

Question

In the context of this exercise, what are some differences between the two representations of a heap?

Answer

In this exercise, it provides the two main ways of representing a heap data structure, either as a binary tree or as an array. In terms of performance, there are not many differences, and their runtimes are the same for almost all functions.

However, there are a few differences for both representations.

Binary tree
In a binary tree representation, we use objects for the Nodes and the Heap itself, which stores all the nodes and functionality. As a result, a binary tree representation usually takes up more memory in a computer.

Binary trees are also slightly more difficult to implement than arrays. However, binary trees can allow for the addition of nodes, without having to worry as much about the heap reaching capacity.

Arrays
Array representations use a data structure like a list to store all the nodes.

Depending on the programming language, heaps represented as arrays can reach their size limit, and require resizing.