1
$\begingroup$

This question is about max heap and array

Suppose there is max heap $h$, with $n$ data items already stored in $h$. An array that is formed by inserting a value larger than all the values in $h$ at the beginning/head of the heap $h$ is assumed to be new array $C$. The array $C$ is a heap (or) not?

My answer: is heap because it's bigger than any other element in array

With $n$ data items already stored in heap $h$, a new array $D$ is created by adding a value $u$ to the heap $h$ that is smaller than any of the $n$ items already stored in heap. If $u$ is added to last element in heap $h$, is array $D$ heap or not?

My answer: it is heap because the smallest one has to be in the leaf

But what is the relation with array? Is there rule to insert node in heap? I know that to insert node to array in heap we insert data as last element of heap and then put it in the root and heapify it.

Improve this question
$\endgroup$
6
  • $\begingroup$ what is the relation with array? especially node thrown in in addition to heap and adding a value $u$ to element in heap. There are two variations of interpreting (the start of) an array as a priority heap, one for 0- or 1-based indexing, each. Even assuming one of these, array [formed] by inserting a value […] at the beginning/head of the heap should have a known interpretation/definition when above questions are asked. $\endgroup$
    – greybeard
    Commented Jan 7, 2020 at 6:58
  • $\begingroup$ @greybeard but how to know if inserting value at top or bottom is heap or not? Is inserting at top heap will make array not heap and inserting at bottom will make heap ? $\endgroup$
    – devss
    Commented Jan 7, 2020 at 9:15
  • $\begingroup$ Without a proper definition of the relation between $h$ and The Array™, I see no way of knowing. Inserting into an array more often than not involves moving all (valid) elements at that index or higher. I can see how appending to the valid elements can be cheap. $\endgroup$
    – greybeard
    Commented Jan 7, 2020 at 9:22
  • $\begingroup$ @greybear Thanks , yes the relation should be to store the heap in the array from index 0 as root until n, that means if i put new element which is bigger than all element in the root heap, and store it directly to array ,which will shift all heap element 1 index higher, the heap is broken right(?) $\endgroup$
    – devss
    Commented Jan 7, 2020 at 9:37
  • $\begingroup$ [shifting all valid array elements] 1 index higher, [storing the new element which is bigger than all older elements at index 0] the heap is broken right? constructing an example where the heap condition is violated should be no harder than giving one condition sufficient it is satisfied after such an operation. Draw your own conclusions regarding your Q&A. $\endgroup$
    – greybeard
    Commented Jan 7, 2020 at 9:47

1 Answer 1

Reset to default
1
$\begingroup$

Suppose an array $A$ is a maxheap. Inserting a large element in the first position of $A$ does not necessarily preserve the maxheap property. The maxheap property requires a node's value to be larger than both its children's values, for each node in the tree. If the value inserted in the first position is larger than all values in the array, then the maxheap property is preserved at the root node, but might not be preserved at some of the other (lower level) nodes.

We can construct an initial array $A$ such that the nodes in the subtree rooted at the right child of the root have much larger values than the nodes in the subtree rooted at the left child of the root. When a new value is inserted in the first position of the array, the tree changes so that the smaller values in the left subtree become parents of the larger values in the right subtree, causing the maxheap property to be violated. For example, take $A=[6,3,5,2,1,4]$, which is a maxheap. Inserting a $7$ in the beginning modifies $A$ to $A=[7,6,3,5,2,1,4]$, which is not a maxheap because the node with value $3$ is a parent of the node with value $4$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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