Prove that any sorted array is a minheap Disprove that a min

Prove that any sorted array is a min-heap. Disprove that a min-heap is a sorted array.

Solution

Technically sorted array is not a min-heap: a min-heap has a binary tree structure where as an array has a random access structure so we can say no they are two very different structures.

But if you interpret the array as having an implied binary tree structure then it can be interpreted as a valid min-heap.

Properties of min-heap tree are:

An array is often interpreted as a binary tree where the children of a given index i

are located at indices (2i+1) and (2i+2) . If size of the array is less than (2i+1) or (2i+2) then consider children of index i are null.

When an array is interpreted in this way, with this implementation of a binary heap, it can be proven that each parent will have a value less than or equal to its two children. Therefore it is a valid min heap.

Here is a proof of why it is a valid min-heap:

Statement: An array of integers sorted in increasing order is a valid min-heap.

we must prove 3 things: each node has at most two children, the (interpreted) tree is complete, and every nodes value is less than the value of each of its children.

   (a) let the binary tree be interpreted such that the children of index i are at indices (2i+1)
for all 2i+1<n and 2i+2 for all 2i+2<n

   (a) let x be defined as a power of 2 such that n/2x<n

   (b) let y be defined as a power of 2 such that ny<2n

   (c) nodes at indices [0,x1] are all internal nodes because the node at index x1 has at least 1 child

   (d) nodes at indices [x,n1] are all leaf nodes because the node at index x

has no children **

   (e) the node at index x1 is the rightmost node in level $h$, where level h
contains nodes at indices [2h1,2h+12]

   (f) statements (a-e) prove statement (2)

To disprove min-heap is not a sorted array: In min-heap each node has two children atmost and every parent has value less than his children but you can\'t say anything about comparison of childrens i.e is either value of left child is greater than right child or right child is greater than left child. So, we can\'t get sorted array in any order of traversal(inorder, preoder etc).