How can the size of a heap be less than its length?

Question

I am studying the heap sort algorithm from the book Introduction to Algorithms by Thomas H. Corman. It differentiates between the length of the array, A.length, as

"the number of elements in the array"

, and A.heapsize, as

"represents how many elements in the heap are stored within array A"

I am trying to visualize a case when A.heapsize will not be equal to A.length.

1. When does an element of a heap not reside in the array?
2. Is there a practical scenario where A.heapsize < A.length?

Answer 1

In general, heaps will support insertion of items. When an element is inserted it is very inefficient to re-allocate the backing array and copy the entire heap just to fit one more element. So the common approach is to either pre-allocate as many elements as you know you need. Or to allocate more than needed, for example by doubling the size of the backing array each time you re-allocate. That way most insertions will not need re-allocation.

When does an element of a heap not reside in the Array?

Never. A.heapsize will always be smaller or equal to A.length

Is there a practical scenario when A.heapsize < A.length?

This would be the common scenario.

This is assuming an 'Array' is fixed length. You can also build your heap on top of a 'dynamic array', that does the re-allocation internally, but the same principle applies. A 'dynamic array' is called vector in C++, List in .Net & Python, ArrayList in Java, but may have another name in your programming language.

Answer 2

I do not have Cormen's book at hand, but almost certainly the "the number of elements in the array" in A.length definition means "the number of cells or buckets available in the array". Depending on the programing tool/language, array cells/positions may be empty, or the may not and will always have a value, albeit possibly invalid. (E.g. positions in an array of integers always have some value, whereas positions in an array of pointers/references may be null/nul/nil.)

As explained in JonasH' answer, the array is just used for storage. As you insert elements in the heap, they are assigned/stored somewhere in the array.

Regarding A.heap-size and "represents how many elements in the heap are stored within array A", here "elements" means valid values, not mere "cells" or "buckets".