heap sort - which heap (min/max) to use for ascending and descending order sort?

Question

I'm noticing a very peculiar thing.

After going through this lecture, I implemented some code for heap-sort in C++.

The code is below.

    template<typename T> void min_heapify(std::vector<T> &vec, int i, int size)
    {
        int left  = (2*i); //left child of a zero-indexed heap (array)
        int right = (2*i)+1; //right child.
        int min;

        min = ( (left<size) && (vec[left] < vec[i]) ) ? left : i;
        min = ( (right<size) && (vec[right] < vec[min]) ) ? right : min;

        if (min!= i)
        {
            swapper(vec[i],vec[min]);
            min_heapify(vec, min, size);
        }
    }
    template<typename T> void build_min_heap(std::vector<T> &vec, int size)
    {
        int i = size/2;
        while(i--)
        {
            min_heapify(vec, i, size);

        }
    }
    template<typename T> void heap_sort(std::vector<T> &vec, int size)
    {
        // build min heap
        build_min_heap(vec, size);
        // then extract min repeatedly.
        while(size>0)
        {
            size--;
            swapper(vec[0],vec[size]);
            min_heapify(vec,0,size);
        }
    }

   int main()
   {
        vector<int> v{14,-1,1000, -999, 3,2,5,10};
        heap_sort(v, v.size());

        return 0;
   }

The peculiar thing is that it makes sense to me that - build a min heap - extract min (or executing min-heapify at the root after building a min heap) should result in ascending order. However, after executing this code and printing out the resultant vector, I get :

1000 14 10 5 3 2 -1 -999 

while trying to make sense of what is going on, I changed

min = ( (left<size) && (vec[left] < vec[i]) ) ? left : i;
min = ( (right<size) && (vec[right] < vec[min]) ) ? right : min;

to

min = ( (left<size) && (vec[left] > vec[i]) ) ? left : i;
min = ( (right<size) && (vec[right] > vec[min]) ) ? right : min;

which actually ends up selecting the bigger(or maximum) of the parent and child nodes, and the resultant vector is :

-999 -1 2 3 5 10 14 1000 

Am I doing something wrong or is my understanding of heap/heap sort unclear? What am I missing here?

Answer 1

Yes the swapper(vec[0],vec[size]); is the extraction. You are extracting the first element into the last element of the vector. Hence getting the opposite result.

The heaps min element is vec[0]. Swapping that to the last position will create a max to min ordering within that vector.

If you implement something like

result.push_back(heap.pop_min());

You will get the ordering you were expecting.