I'm new to such complicated (for me) data structures as binary trees now. I think I've made many mistakes in my build_max_heap algorithm and it can be improved. The rule I'm using is that smaller trees rooted at left(n) and right(n) (n is the index) are max heaps itself. I don't care about the variables for size of array and filling the array now, it's just the static version to implement the algorithm of build_max_heap. I'm moving from the root down the tree; by the way, the majority of textbooks let us move from the bottom to the root, but in my situation it doesn't work, what is the reason?.. I also preferred not to use recursion.
int left(int n){
return 2 * n;
}
int right(int n){
return 2 * n + 1;
}
void max_heapify(int(&A)[16], int n){
int largest = 0;
int l = left(n);
int r = right(n);
cout << "A[" << n << "]" << ": " << A[n]<< endl;
cout << "A[l]: " << A[l] << endl;
cout << "A[r]: " << A[r] << endl;
if (l <= 16 && A[l] > A[n]){
largest = l;
}
if (r <= 16 && A[r] > A[n]){
largest = r;
}
else largest = n;
if (largest != n){
cout << A[n] << "[" << n << "]" << " is replaced with " << A[largest] << "[" << largest << "]" << endl;
int temp = A[n];
A[n] = A[largest];
A[largest] = temp;
}
cout << endl;
}
void build_max_heap(int(&A)[16], int size){
for (int i = 1; i <= size/2; i++){
max_heapify(A, i);
}
}
int main(){
int A[16] = { 0, 40, 11, 9, 14, 17, 18, 20, 3, 6, 9, 14, 16, 17, 10, 15 };
build_max_heap(A, 16);
for (int i = 0; i < 16; i++){
cout << A[i] << " ";
}
cout << endl;
return 0;
}