2

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?
Improve this question
5
  • 1
    Pretty much through whole heap sort the heap's size (1 to n-1 when building it and n-1 to 0 when taking elements out) is less than the size of array... you may want to re-read the algorithm... Commented Aug 5, 2021 at 5:37
  • 2
    I think what's confusing you is the wording. The heap data structure is conceptually a tree, and you could build it as a tree of separate objects in code, but it has a convenient representation as an array, where parent-child relationships between the nodes are implicit (they are governed by a convention that determines which node goes at which index). The heapsort algorithm uses this fact; an input array of elements to sort is given to the procedure, which initially uses the array to make a heap out (the whole) of it; a side effect of that is that the largest element is found. 1/2 Commented Aug 5, 2021 at 10:27
  • 1
    It then takes that element and puts it at the back, to start building the sorted part of the input array. So the heap part has now shrunk. The input array is split into two parts. The part of the array that "houses" the heap keeps shrinking, making room for the sorted part to grow. A.heapsize just tells you, at any point during the execution, where the heap-containing part ends (and where the sorted array starts). You need this because the split is not physical (it's not actually two arrays) - you just maintain a "marker" to tell you where each part starts/ends. 2/2 Commented Aug 5, 2021 at 10:27
  • @FilipMilovanović, isn't the sorted part also part of the heap in heap sort, based on whether the algorithm is a min-heap or a max-heap? Commented Aug 6, 2021 at 4:45
  • 1
    "isn't the sorted part also part of the heap" - no, if it were, that would violate the heap property, as it's sorted in the opposite way. E.g. in a max-heap, each subtree contains only elements <= than the root. So, at the top of the tree is the largest number, and then the numbers drop off as you follow the branches. But in the sorted part, it starts with some number and then it grows (but note that you're building the sorted part backwards). The heap thing just lets you find the next largest element in the unsorted part quickly, you don't want to include the sorted part in it. Commented Aug 6, 2021 at 17:40

2 Answers 2

Reset to default
13

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.

Improve this answer
0
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".

Improve this answer
2
  • Correct me if I am wrong, but as far as I remember, a classic heap is usually a data structure which does not require empty cells in the middle, so the "heap size" does indeed correspond to the number of elements in a contiguous array (which might be an array having a larger storage capacity internally, of course). Commented Aug 6, 2021 at 12:15
  • @DocBrown Indeed. The classic array representation of a classic heap uses contiguous cells/positions in a (as you say, possibly larger) array. Commented Aug 7, 2021 at 18:42

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.