fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class MinHeap {
  5. public:
  6.     int *arr;
  7.     int size{0};
  8.     int capacity{1000};
  9.  
  10.     MinHeap() {
  11.         arr = new int[capacity];
  12.         size = 0;
  13.     }
  14.  
  15.     ~MinHeap() {
  16.         delete[] arr;
  17.         arr = nullptr;
  18.         size = 0;
  19.     }
  20.  
  21.     int leftchild(int node) {
  22.         int ans = 2 * node + 1;
  23.         return ans >= size ? -1 : ans;
  24.     }
  25.  
  26.     int rightchild(int node) {
  27.         int ans = 2 * node + 2;
  28.         return ans >= size ? -1 : ans;
  29.     }
  30.  
  31.     int parent(int node) {
  32.         return node == 0 ? -1 : (node - 1) / 2;
  33.     }
  34.  
  35.  
  36.  
  37.     //Problem 4
  38.     bool isHeap(int *arr, int size){
  39.         //only non leaf
  40.         for (int i = 0; i < size / 2; i++) {  
  41.         int left = leftchild(i);
  42.         int right = rightchild(i);
  43.  
  44.         if (left < size && arr[i] > arr[left]) return false;  
  45.         if (right < size && arr[i] > arr[right]) return false; 
  46.         }
  47.         return true;
  48.     }
  49. };
  50. int main(){
  51.  
  52.     MinHeap h;
  53.     int heap1[] = {1, 3, 5, 7, 9, 6, 8};  // Min Heap ✅
  54.     int heap2[] = {10, 20, 30, 40, 50, 60, 70}; // Min Heap ✅
  55.     int notHeap[] = {10, 5, 15, 20, 25, 30, 35}; // Not a Heap ❌
  56.  
  57.     cout << boolalpha <<h.isHeap(heap1, 7) << "\n"; 
  58.     cout <<boolalpha<< h.isHeap(heap2, 7) << "\n"; 
  59.     cout <<boolalpha<< h.isHeap(notHeap, 7) << "\n"; 
  60.     return 0;
  61. }
Success #stdin #stdout 0.01s 5300KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
true
true
false
https://ideone.com/uoA2X1
language:
C++ (gcc 8.3)
created:
7 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!