Question

write a function that determines if a given vector of integers is a min–heap. By default, a vector is asemi–heap satisfying the heap structure propertybut not the heap order property.

Input

There is an unknown number of integer data that will be provided from standard input. Each line of input represents the contents of a vector. We do not know how many lines of input there are.

1 2 3 4 5

5 4 3 2 1

1 9 2 13 10 5 3 15 14 11 21 7 6 4 17 16 24 28

25 32 55 97 43 62 30 2 27 59 15 81 22 97 38 42

Output

The only output is a determination whether each provided vector of integers is a min–heap or not. If it is not amin–heap, report the largest index where themin–heap order property is violated.

Sample output, corresponding to the sample input above, is provided below.

Vector is a min-heap.

Min-heap order property violated at index 1.

Vector is a min-heap.

Min-heap order property violated at index 5.

Answer 1

Min-Heap:

A Min Heap is a Complete Binary Tree, In which the value of the parent node is smaller than both of its children's value. And due to its property of being complete, it can be represented using an array representation.

For element at index i, its children in the array can be found at (2*i+1) (left child) and (2*i+2) (right child).

Now in order to check if a vector follows the min-heap property or not, we will have to iterate through every value in vector and check if it is less than its children.

C++ Code:

#include
using namespace std;

// this funtion returns an index i (0<=i // And returns v.size() if vector is a heap
int is_vector_heap(vector v)
{
int n = v.size();
//iterate through all values in vector
for (int i=0; i {
//find left child index
       int left = 2*i+1;
       int right = 2*i+2;
      
       // we need to check the existance of children because for leaf nodes there will be no children
       // if left child exists and its value is less than parent then return index i
if(left return i;
  
// if right child exists and its value is less than parent then return index i
if (right < n && v[left] < v[i])
return i;
}
return n;
}
int main()
{
   string line;
  
   //read input line by line until a empty line is entered
   while (std::getline(std::cin, line) && !line.empty())
   {
       //parse the line to build a vector of integers
       istringstream iss;
       iss.str(line);
       vector v;
       while (!iss.eof())
       {
       int num;
       iss >> num;
       v.push_back(num);
       }
       //check if v is a min-heap
       int i=is_vector_heap(v);
       if(i==v.size())
   {
       cout<<"Vector is a min-heap.\n";
       }
       else
       {
           cout<<"Min-heap order property violated at index "<        }
   }
}

Sample Output: