Search code examples
c#algorithmsortingheapmin-heap

Is minimum heap sorted by "default"

I just picked up "Introduction to algorithms", and I started implementing heaps and heapsort algorithm in c#.

Implementing a function that constructs a min/max heap from an array of doubles, i noticed that the constructed heap has some interesting properties.

A built minimum heap can be read left to right, and top to bottom (from root to leaves, by levels), and it will be sorted.

Is this a property of a minheap, or I am just unable to get a case which this property does not apply. Max heap doesnt work this way, atleast what i am getting here.

Output:

2345 7 34 6 3 5 4 5 1 2 3 2 1 3 1 3 2 1 (maxheap)

1 1 1 1 2 2 2 3 3 3 3 4 5 5 6 7 34 2345 (minheap)

Thanks for any responses in advance!

Solution

  • Heaps only have relation between Parent node and their respective child nodes. There is no relation between nodes at same level.

    For Min Heaps: Value of Parent node <= Value of its child nodes
For Max Heaps: Value of Parent node >= Value of its child nodes

    So its not necessary for Min Heap to be sorted when travelled Top-to-Bottom,Left-to-Right. Its just a coincidence in your case.
    For eg: Consider this sequence: 1, 3, 2, 5, 4, 10, 9 Heap for above sequence
    These are in MinHeapify order but clearly not in sorted order.
    Visit this Interactive Heap Link or this link for proper visualisation on how heap is built.