Would building a max heap from an Unsorted array would follow Binary Tree properties?

Question

Given an unsorted array of size 10

int[] arr={∞,1,2,3,4,5,6,7,8,9,10};

If I execute code

public void build_heap(){
            for(int i=size/2;i>=1;i--)
                    max_heapify(i);
}

The resulting array in what case follow binary tree properties

( ie left subtree < root & root < right subtree )

? How to generate such an array ?

Is this the right approach : Instead of using build_heap , keep I will keep inserting the element into the heap ? (Is there a better solution?)

Answer 1

No, you are confused on your data structures.

Heaps do not guarantee an ordering in the way a BST(binary search tree) does. Heaps only guarantee that a given node's children satisfy the heap property (ie. either they are all less than the given subtree root for a max heap, or greater for a min heap).

BST's on the other hand, guarantee that a given subtree's root has all keys that are less than the root's key on the left subtree, and all keys greater than on the right subtree.

edit: you could run heapsort on a heap to generate a sorted array in nlogn time, from which you could construct a balanced BST in linear time.