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.     }
  13.  
  14.     ~MinHeap() {
  15.         delete[] arr;
  16.         arr = nullptr;
  17.     }
  18.  
  19.     int leftchild(int node) {
  20.         int ans = 2 * node + 1;
  21.         return ans >= size ? -1 : ans;
  22.     }
  23.  
  24.     int rightchild(int node) {
  25.         int ans = 2 * node + 2;
  26.         return ans >= size ? -1 : ans;
  27.     }
  28.  
  29.     int parent(int node) {
  30.         return node == 0 ? -1 : (node - 1) / 2;
  31.     }
  32.  
  33.     void heapifyUp(int child_pos) {
  34.         int parent_pos = parent(child_pos);
  35.         if (child_pos == 0 || parent_pos == -1 || arr[parent_pos] < arr[child_pos]) {
  36.             return;
  37.         }
  38.         swap(arr[parent_pos], arr[child_pos]);
  39.         heapifyUp(parent_pos);
  40.     }
  41.  
  42.     void push(int node) {
  43.         assert(!isFull());
  44.         arr[size++] = node;
  45.         heapifyUp(size - 1);
  46.     }
  47.  
  48.     void heapifyDown(int parent_pos) {
  49.         int left_child = leftchild(parent_pos);
  50.         int right_child = rightchild(parent_pos);
  51.         int min_child = parent_pos;
  52.  
  53.         if (left_child != -1 && arr[left_child] < arr[min_child]) {
  54.             min_child = left_child;
  55.         }
  56.  
  57.         if (right_child != -1 && arr[right_child] < arr[min_child]) {
  58.             min_child = right_child;
  59.         }
  60.  
  61.         if (min_child != parent_pos) {
  62.             swap(arr[parent_pos], arr[min_child]);
  63.             heapifyDown(min_child);
  64.         }
  65.     }
  66.  
  67.     void pop() {
  68.         assert(!isEmpty());
  69.         swap(arr[0], arr[--size]);
  70.         heapifyDown(0);
  71.     }
  72.  
  73.     int top() {
  74.         assert(!isEmpty());
  75.         return arr[0];
  76.     }
  77.  
  78.     bool isEmpty() {
  79.         return size == 0;
  80.     }
  81.  
  82.     bool isFull() {
  83.         return size == capacity;
  84.     }
  85.  
  86.     void print_less_than(int val, int parent_pos = 0) {
  87.     if (parent_pos >= size || arr[parent_pos] >= val) {
  88.         return;
  89.     }
  90.  
  91.     cout << arr[parent_pos] << " ";
  92.  
  93.     int left = leftchild(parent_pos);
  94.     int right = rightchild(parent_pos);
  95.  
  96.     if (left != -1) {
  97.         print_less_than(val, left);
  98.     }
  99.     if (right != -1) {
  100.         print_less_than(val, right);
  101.     }
  102. }
  103.  
  104. };
  105.  
  106. int main() {
  107.     MinHeap heap;
  108.     heap.push(7);
  109.     heap.push(1);
  110.     heap.push(5);
  111.     heap.push(2);
  112.     heap.push(3);
  113.  
  114.     cout << "The heap traversal is:\n";
  115.     while (!heap.isEmpty()) {
  116.         cout << heap.top() << " ";
  117.         heap.pop();
  118.     }
  119.     cout << '\n';
  120.  
  121.     MinHeap mn;
  122.     mn.push(1);
  123.     mn.push(5);
  124.     mn.push(2);
  125.     mn.push(3);
  126.     mn.push(4);
  127.     mn.push(6);
  128.  
  129.     cout << "Print elements less than 6:\n";
  130.     mn.print_less_than(6, 0);
  131.     cout << '\n';
  132.  
  133.     return 0;
  134. }
  135.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
The heap traversal is:
1 2 3 5 7 
Print elements less than 6:
1 3 5 4 2
https://ideone.com/w9B92d
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!