Heapsort Algorithm using min-heap

Question

When I implement heapsort using a min-heap it sorts the array from largest to smallest. Is this the desired output for a heapsort using min-heap? It seems redundant to sort again to output smallest to largest after the sort is complete since the heap itself has a smallest to largest structure.

CODE:

#include <iostream>
#include <vector>
#include "random.h"
#include "print.h"
int parent(int i)
{
    return (i - 1) / 2;
}
int left(int i)
{
    if(i == 0)
        return 1;
    else
        return 2*i;
}
int right(int i)
{   if(i == 0)
        return 2;
    else
        return 2*i + 1;
}
void min_heapify(std::vector<int> &A, int i, int heapsize)
{
    int smallest;
    int l = left(i);
    //std::cout << "left = " << l << std::endl;
    int r = right(i);
    //std::cout << "right = " << r << std::endl;
    if(l <= heapsize && A[l] < A[i])
        smallest = l;
    else
        smallest = i;
    //std::cout << "smallest = " << smallest << std::endl;
    if(r <= heapsize && A[r] < A[smallest])
        smallest = r;
    if(smallest != i) {
        print(A);
        exchange(A, i, smallest);
        min_heapify(A, smallest, heapsize);
    }
}
void build_min_heap(std::vector<int> &A)
{
    int heapsize = A.size() - 1;
    for(int i = (A.size() - 1) / 2; i >= 0; i--)
        min_heapify(A, i, heapsize);
}
void heapsort(std::vector<int> &A)
{
    int heapsize = A.size() - 1;
    build_min_heap(A);
    std::cout << "heapsort after buildmaxheap" << std::endl;
    print(A);
    for(int i = A.size() - 1; i > 0; i--) {
        exchange(A, 0, i);
        heapsize--;
        std::cout << "heapsize = " << heapsize << std::endl;
        min_heapify(A, 0, heapsize);
    }
}
int main()
{
    std::vector<int> B;
    fill(B, 5);
    print(B);
    heapsort(B);
    print(B);
    return 0;
}

Output from code:

41 65 31 41 19 
41 65 31 41 19 
41 65 19 41 31 
41 19 65 41 31 
41 19 31 41 65 
19 41 31 41 65 
heapsort after buildmaxheap
19 31 41 41 65 
heapsize = 3
65 31 41 41 19 
31 65 41 41 19 
heapsize = 2
heapsize = 1
65 41 41 31 19 
heapsize = 0
65 41 41 31 19 

Output for 20 elements:

41 65 31 41 19 15 72 11 78 69 37 23 29 63 75 4 5 49 75 99 
after buildmaxheap
4 5 15 11 19 23 29 41 31 69 37 41 72 63 75 65 78 49 75 99 
after sort
99 78 75 75 72 69 65 63 49 41 41 37 31 29 23 19 15 11 5 4 

Volkan

Can you show your code? – Unlade

Let there be a binary tree on the heap. To sort an array, you insert elements one by one into the tree. Obvioussly, the elements are in a certain order in the tree, but you want them back in an array. So you traverse the tree taking the smallest elements first and you put them back into an array. – Stratocracy

Related blog post and demo code. – Skyline

Answer 1

Order: Use max-heapify to sort in asceding order, min-heapify to sort in descending order.

Sorting: Building the heap with min-heapify does not sort your array; it only enforces the (weaker) min-heap property, that is

A[parent(i)] <= A[i]

for every node i other than the root. After the heap is built, the root (leftmost position in the array) has the minimum element. Sorting then repeatedly moves elements from the root to the right and calls min-heapify on the root (bringing there the minimum of what remains), hence the descending order.

The code you are posting appears correct at a glance but does not compile as is, so I cannot test. If your array appears sorted right after building the heap, it should be a coincidence. Try a larger test.

Evaporate

Try 15-20 elements and you'll see! – Evaporate

When you say my array appears sorted, you mean after I build the heap? – Volkan

I posted my output with 20 elements. Is this heap wrong? It's not in sorted order but I don't think it needs to be. All the child nodes are smaller in value than the parent node. – Volkan

@Comrade Yes. Your output shows 19 31 41 41 65 right after building the heap. You say this is sorted, but it only satisfies the min-heap property, which happens to be the same in this case. Min-heap property only says 19 <= 31, 19 <= 41, 31 <= 41, 31 <= 65. – Evaporate

Yes. I should have tested the output with different sizes. But it does satisfy the min heap property which is what I was after in that step. My ultimate question was that when I use min-heap if the purpose was to sort in descending order whereas max-heap is in ascending order. You say yes, but the other answer says I should fix the code to put it in ascending order. – Volkan

@Comrade The output @20 elements seems fine. If your only problem is the order and you need it ascending, then all you need to change is the comparison < -> > between elements to make a max-heap instead. Typically you'd use a comparison functor as a parameter. – Evaporate

Yes. That is all I was really asking. If the purpose of using a min-heap was to sort in descending order. I am glad I asked though because the first output coincidentally had the elements sorted and I had believed that building the heap was also sorting the elements, which it wasn't of course. – Volkan

Answer 2

Normally you use a max-heap to sort in ascending order, because its easier. Using a max-heap, you 'float' the max to the front, and build the sorted list from the back.

If you want to use a min-heap to sort in ascending order, you have to build it backwards. (ie the lowest is the last index ). Otherwise you will be churning your heap.

start 18 70 6 13 12 55 
min-heap(backwards) -> 18 70 55 13 12 6
then
swap  6 w 18 -> 6, 70 55 13 12 18 -> sink 18 -> 70 55 13 18 12
swap 12 w 70 -> 6 12, 55 13 18 70 -> sink 70 -> 55 70 18 13
swap 13 w 55 -> 6 12 13, 70 18 55 -> sink 55 -> 70 55 18
swap 18 w 70 -> 6 12 13 18, 55 70 -> sink 70 -> 70 55
swap 55 w 70 -> 6 12 13 18 55, 70 
done

Passionless

That seems to defeat the purpose of building a heap in the first place. – Volkan

Answer 3

I was just wondering about that very problem ( isn't Heap sort having an extra step at the end, the unnecessary swapping of elements. Just use min-heaps and let call min-heapify and get your work done).

Regarding this way, we could have achieved O(logn) time which somewhat disqualifies the binary decision tree model - which says O(nlogn) is acceptable tightest upper bound on comparison sorting algorithms.

The short answer is: heap data structure aren't binary search trees. A heap may guarantee ordering of elements in sorted top->bottom way, but a binary search tree guarantees they'll be ordered left to right as well. We were just mixing up binary trees and heaps.

A min heap only guarantees ,

Amin[Parent]<=A[either_of_the_children] // says nothing about ordering of children

Here is a binary tree (although unbalanced and not sorted) :

And here is a Heap :

Hope you get my point. If still not, then think of it as, a min heap represented an array guarantees that parent is smaller than its child, but says nothing about are all children arranged in sorted order left to right? We'll still be performing min-heapify on each child of current root to be swapped.

Toastmaster

a heap IS a binary tree (a parent can have max 2 children), but it isn't a binary SEARCH tree (left child < right child) – Geddes