Why loop starts with i = n/2 for doing heap sort?

Question

I need to change max-heap code to min-heap code. I changed some parts, but when I print, I get only the min-heap array by order, not sorted.

#include <iostream>
#include <fstream>
#define MAX_TREE 100

using namespace std;

typedef struct {
    int key;
}element;

element a[MAX_TREE];

void SWAP(element root, element target, element temp) { 
    root = target;
    target = temp;
}
void adjust(element e[], int root, int n) { //array로 입력된 tree를 min heap으로 adjust(조정해서) sort
    /*adjust the binary tree to etablish the heap*/
    int child, rootkey;
    element temp;
    temp = a[root]; //root element assign
    rootkey = a[root].key; //root element's key value
    child = 2 * root; //root ( a[i] )의 left child
    //leftChild: i * 2 (if i * 2 <= n) rightChild: i * 2 + 1(if 1 * 2 + 1 <= n)
    while (child <= n) { //if child exists
        if ((child < n) &&//compare left child with right child 
            (a[child].key > a[child + 1].key))//
            //if leftChild.key > rightChild.key
            child++;//move to smaller child
        if (rootkey < a[child].key) //if it satisfies min heap
            break; //break when root key is smaller than child's key
        else { //if it doesn't satisfies min heap
            a[child / 2] = a[child];
            //assign child to parent
            child *= 2; 
            //loop until there's no child
        }
    }
    a[child / 2] = temp; //if there's no more child, assign root element to child/2
}
void heapSort(element a[], int n) {
    /*perform a heap sort on a[1:n]*/
    int i;
    element temp;
    temp = a[1];

    for (i = n / 2; i > 0; i--) { //<-This is the part I don't understand
        adjust(a, i, n);
    }
    for (i = n - 1; i > 0; i-- ) {
        SWAP(a[1], a[i + 1], temp);
        adjust(a, 1, i);
    }
}
void P1() {
    int n;
    std::fstream in("in1.txt");
    in >> n;
    printf("\n\n%d\n", n);
    for (int i = 1; i <= n; i++) {
        element temp;
        in >> temp.key;
        a[i] = temp;
    }
    heapSort(a, n);
    //6 5 51 3 19 52 50
}

int main() {
    P1();
} 

It's my professor's example code. I need to input numbers from file in1.txt. In that file there are values for n, m1, m2, m3...

n is the number of key values that will follow. Following m1, m2, ... are the key values of each element.

After getting input, I store integers in an array that starts with index [1]: it's a binary tree represented as an array.

I need to min-heapify this binary tree and apply heapsort.

This code was originally max-heap sort code. There are maybe some lines I missed to change.

I don't get why I need to start for statement with i = n/2. What's the reason?

Answer 1

Why for statement starts with i=n/2?

This is the part I don't understand

This loop:

for (i = n / 2; i > 0; i--) {
    adjust(a, i, n);
}

... is the phase where the input array is made into a heap. The algorithm calls adjust for every internal node of the binary tree, starting with the "last" of those internal nodes, which sits at index n/2. This is Floyd's heap construction algorithm.

There would be no benefit to calling adjust on indexes that are greater than n/2, as those indices represent leaves in the binary tree, and there is nothing to "adjust" there.

The call of adjust will move the value at the root of the given subtree to a valid position in that subtree, so that that subtree is a heap. By moving backwards, this accumulates to bigger subtrees becoming heaps, until also the root is a heap.

The error

The error in your code is the SWAP function. As you pass arguments by value, none of the assignments in that function impact a.

Correction:

void SWAP(element &root, element &target) { 
    element temp = root;
    root = target;
    target = temp;
}

And on the caller side, drop temp.