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

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. — cpp
– cpp, Commented Sep 20, 2013 at 17:38

iavr · Accepted Answer · 2013-09-20 18:01:42Z

5

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.

edited Sep 20, 2013 at 18:01

answered Sep 20, 2013 at 17:38

iavr

7,6671 gold badge21 silver badges53 bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

iavr Over a year ago

Try 15-20 elements and you'll see!

Mars Over a year ago

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

Mars Over a year ago

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.

iavr Over a year ago

@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.

Mars Over a year ago

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.

|

Sanjaya R · Accepted Answer · 2013-09-20 22:37:08Z

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

edited Sep 20, 2013 at 22:37

answered Sep 20, 2013 at 17:37

Sanjaya R

6,4662 gold badges20 silver badges19 bronze badges

1 Comment

Mars Over a year ago

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

Abhinav Gauniyal · Accepted Answer · 2017-12-09 04:13:45Z

2

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) :

Binary tree

And here is a Heap :

min 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.

edited Dec 9, 2017 at 4:13

answered May 13, 2015 at 12:32

Abhinav Gauniyal

7,6549 gold badges54 silver badges97 bronze badges

1 Comment

Ahmed Fwela Over a year ago

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)

Collectives™ on Stack Overflow

Heapsort Algorithm using min-heap

3 Answers 3

7 Comments

1 Comment

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

7 Comments

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related