Is a sorted array a min-heap? What's the minimum value of a max-heap?

Question

I have studied min-heaps and max-heaps, and I have a couple of questions:

1. Is a sorted array a min-heap?
2. What is the minimum value of a max-heap?

Aerobiology

Answer 1

An array sorted from lowest to highest is a min-heap when using the array-based heap implementation. The min-heap property that the parent node value is less than or equal to it's child nodes (2i + 1 and 2i + 2, using zero-based arrays) holds for all nodes that have children.

The minimum value of a max heap is in one of the leaf nodes, but you don't know which. Since the minimum node cannot, by definition, have any child nodes, it must be a leaf. The heap property, however, does not specify how leaf nodes compare with each other, only with their parent.

Aargau

Answer 2

Is a sorted array a min-heap?

Yes, if you're using the typical array-stored heap convention.

Where is the minimum value of a max-heap?

At one of the leaves. Which exactly is undefined.

Copolymerize

Answer 3

You can implement binary heap as a array for index i compare with 2*i+1 and 2*i+2 (i starts from 0). in min heap a[i] < a[2*i+1] and a[i] < a[2*i+2]

so

1 . A sorted array is a min heap.

2 . It hasn't specific index. All we know that it is just a leaf

I suggest you read this http://en.wikipedia.org/wiki/Binary_heap

Woermer

Answer 4

where is the minimum value of a max heap?

Ans: Max heap can be represented using simple array with index start from 1 to n. 1st element is the root of the max heap. Heap property: The node at index i has left child at 2i and right child at 2i+1 (if 2i and 2i+1 are less than heap size i.e. array length).

Leaf nodes of the max heap are found from index i+1 to n. Here i=n/2; n is array length. And one of the leaf nodes has the minimum value.
So we can find the minimum value of max heap from the values of a[i+1] to a[n]. Time complexity to find minimum value is order-of(n-i).

Rovner

Answer 5

• a sorted array is a min heap?

If it is ordered ascending - yes, generally speaking it is a min heap, more precisely - an array implementation of a binary heap with the following rules:

• Children of the node with index i can be found at indexes 2i + 1 and 2i + 2
• The parent of the node with index i can be found at index floor((i - 1)/2)

At the same time, it doesn't work in reverse - an array-based binary heap will not store a sorted list.

• where is the minimum value of a max heap?

It is not defined, and it is not the question that you want to answer quickly when you store your keys in a min heap. If you want to be able to peek both min and max of the heap in O(1) time, you can use classes like MinMaxPriorityQueue in Java.

Rabato

Answer 6

Is a sorted array a min-heap?

sorted array is either min-heap or max-heap but vice versa is not true
min-heap or max-heap are not necessarily sorted arrays.

What is the minimum value of a max-heap?

max-heap (or priority queue) by definition provides max value from a collection in O(1) time. if anyone is required to retrieve min value from a max-heap then using heap itself in the first place for this problem is not right. it's like expecting a stack provide FIFO access or expecting queue to provide LIFO access.

But jfyi , min value will be at one of the leaves of the tree formed by heap. it could be on any subtree. so you need another algorithm which will take more than O(1) time to locate it.

As a side note:
A heap with n elements may have [ 1 to (n+1)/2] leaves.
If height of the tree formed by heap is h then heap will have upto 2^(h-1) leaves

Fellini

Answer 7

Arrays either can be sorted in ascending order or in descending order. The statement "A sorted array is min-heap" is partially correct. The correct version of this statement is "An array sorted in ascending order is can be treated as min- heap" and its complementry statement is "An array sorted in descending order can be treated as max heap".

"An array sorted in ascending order is can be treated as min- heap"

But remember that "Not all min-heaps can take the form of array sorted in ascending order".

And about minimum value of max heap we only know that this is present in the leafs and we can search that in O(n)

Culmination

Answer 8

Always True Fact is :

Every sorted list in ascending order is a minheap.

Try and test it, there is no exception about this rule!

Cavefish