0
$\begingroup$

I was trying to understand the concept of Max-Heap. And to my understanding its a complete binary tree and each parent has a value greater than its children.The example I was going though had the following array which it said was a Max-Heap.

BookArray [] = {45,10,11,3,2,7,9,1,0}

I then decided to shuffle the elements (so they are no longer in binary heap) and got this.

Shuffled[] = {11,1,0,7,9,3,2,10,45}

I then decided to write a program that would sort the elements in the array in Min-Heap so I got this array

Sorted[] = {45,11,3,10,7,0,2,1,9}

My question is if my sorted array is also a valid max-heap ? since my array does not match the bookArray

$\endgroup$
  • 2
    $\begingroup$ go through the definition of Max and Min heap. it is a Max heap(not Min). $\endgroup$ – tanmoy Mar 22 '14 at 18:27
  • $\begingroup$ Sorry .. got confused. Let me fix the question $\endgroup$ – Rajeshwar Mar 22 '14 at 18:29
2
$\begingroup$

The (binary) heap data structure is an array object that can be viewed as a nearly complete binary tree, the tree is completely filled on all levels except possibly the lowest.

Min Heap has the property:for every node i (except root node) Array[parent(i)]<=Array[i]. So the smallest element in a min-heap is at the root.

Max Heap is organized in opposite way, i,e. it has the property: for every node i (except root node) Array[parent(i)]>=Array[i]. So the largest element in a Max-heap is at the root.

You can check if the array is maintaining the heap property by the following algorithms.

Algorithm 1

Parent(i)    
    return floor(i/2)  

Algorithm 2

Left(i)  
    return 2*i

Algorithm 3

Right(i)  
   return 2*i+1

Now you can check on your own that if your array maintaining Max heap property or not.

It is not mandatory that two heaps with same elements have same arrangement.The thing you have to be conform that if all elements are maintaining the heap property or not.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.