Heap_size in heap_sort

Question

I'm reading Cormen's "Introduction to Algorithms", and I'm trying to implement a heap-sort, and there's one thing I continually fail to understand: how do we calculate the heap_size for a given array? My textbook says

An array A that represents a heap is an object with two attributes: A.length, which (as usual) gives the number of elements in the array, and A.heap-size, which represents how many elements in the heap are stored within array A. That is, although A[1 .. A.length] may contain numbers, only the elements in A[1..A.heap-size],where 0 <= A.heap-size <= A.length, are valid elements of the heap.

If I implement an array as std::vector<T> Arr, then its' size would be Arr.size, but what would its' heap_size be is currently beyond me.

Answer 1

The heap size should be a separately stored variable, which you manage yourself.

Whenever you remove from or add to the heap, you should decrement or increment the value appropriately.

In C++, using a vector, you may actually be able to use the size, since the underlying representation is an array that's at least as big as the size of the vector, and it's guaranteed to stay the same size if you call resize with a smaller size. (So the underlying array will be the array size and the vector size will be the heap size).