[Solved]: Is this a proper Max Heap Data Structure

Problem Detail: 

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

Asked By : Rajeshwar

Answered By : tanmoy

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/22941