The most appropriate way to implement a heap is with an array rather than a linked list, why is this?

The most appropriate way to implement a heap is with an array rather than a linked list, why is this?

I don't completely comprehend why this is? is it because it is easier to traverse?

It doesn't make any sense at all to implement a heap as a linked list. (The most common kinds of) heaps are inherently binary trees. You can store a heap in an array because it's easy to compute the array index of a node's children: the children of the node at index K live at indices 2K+1 and 2K+2 if indices start at 0 (or at indices 2K and 2K+1 if indices start at 1). It's massively more efficient to find the Kth element of an array than the Kth element of a linked list.

Advantages of storing a heap as an array rather than a pointer-based binary tree include the following.

• Lower memory usage (no need to store three pointers for every element of the heap).

• Easier memory management (just one object allocated, rather than N).

• Better locality of reference (the items in the heap are relatively close together in memory rather than scattered wherever the allocator put them).

StackExchange Computer Science Q#41719, answer score: 13