How to check if an array is a mini-heap?

Question

I have the following array. How to check if an array containing n elements is min heap?

Answer 1

Since your index starts at 1, (index 0 contains 0 - why?), You can define the data index of the node data as follows:

• Let the index of this node be i
• Pointer i left child: 2i
• Child Rights Index i : 2i + 1

Thus, for each node, you can easily verify that both children are larger than the node itself.

Answer 2

is_heap is a great offer. You just need to use the correct comparator. And you can even use it with 1-based indexing using iterators effortlessly:

 #include <iostream> #include <algorithm> #include <vector> #include <functional> int main() { std::vector<int> v {0, 5, 9, 11, 14, 18, 19 }; std::cout << std::is_heap( v.begin()+1, // off by 1 v.end(), std::greater<int>() // std::less is used by default for max-heap ); } 

Answer 3

The famous Breadth First Search (BFS) can also be used to check if a tree is a minimum / maximum heap or not.

 #include <iostream> #include <queue> int main() { int tree[] = {5, 9, 11, 14, 18, 19, 21, 33, 17, 27}; int size = 10; std::queue <int> q; q.push(0); bool flag = true; while(!q.empty()) { int x = q.front(); q.pop(); int left = 2*x+1, right = 2*x+2; // 0-based indexing used here if(left < size) { // check if left child exists or not. q.push(left); // check value at parent is less than child or not. if(tree[x] > tree[left]) { flag = false; break; } } if(right < size) { // check whether right child exists or not. q.push(right); if(tree[x] > tree[right]) { // check value of parent less than child. flag = false; break; } } } if(flag) std::cout << "It is minimum heap.\n"; else std::cout << "Not a minimum heap.\n"; return 0; } 

The idea is similar to the idea of wookie919 .