What is the difference between A.length and A.heap-size?

Question

I have a question about heap sort. It state in an Algorithms book that A.heap-size<= A.length I don’t understand the difference between the two. If an array represents a heap, why is there a possibility that A.heap-size is less than A.length. I know that A.heap-size represents the number of elements inside a heap, so why is it not completely only equal to the number of items inside an array?

Answer 1

Just to expand an answer. Read further that book.

A.heap_size of an array, is that place where heap (max_heap or min_heap) structure elements will be placed. It makes sense in scope of sorting or queuing. You are right: this is the number of elements inside a heap, but it's equal to A.length only at first iteration of heap sort.

At next iteration, after exchanging root of the max_heap tree (A[1]) with A[i] = A[A.length] (last element inside array A), the A[1] element will be the last element of the A, and A.heap_sort value will be decreased by 1 and max_heap structure should be max_heapified: A[Parent(i)] >= A[i], where Parent(i) returns i/2 of heap tree.