fork(1) download 
  1. #pragma once
  2. #include <iostream>
  3. using namespace std;
  4.  
  5.  
  6. const int SIZE = 20;
  7. class Heap {
  8. private:
  9.   int arr[SIZE];
  10.   int n;
  11.  
  12.   void heapUp(int child);
  13.   void heapDown(int parent);
  14.   //convenience
  15.   int left(int i) { return 2 * i + 1; }
  16.   int right(int i) { return 2 * i + 2; }
  17.   int parent(int i) { return (i - 1) / 2; }
  18.  
  19. public:
  20.   Heap(void);
  21.   ~Heap(void);
  22.  
  23.   void insert(int value);
  24.   int remove();
  25.   void print();
  26.   void sort();
  27. };
  28.  
  29.  
  30.  
  31. #include "Heap.h"
  32.  
  33. Heap::Heap(void) { n = 0; }
  34. Heap::~Heap(void) {}
  35. void Heap::insert(int value) {
  36.   if (n == SIZE)
  37.     exit(1);
  38.   arr[n] = value;
  39.   heapUp(n++);
  40. }
  41. void Heap::heapUp(int i) {
  42.   int p = parent(i);
  43.   if (arr[i] > arr[p]) {
  44.     swap(arr[i], arr[p]);
  45.     heapUp(p);
  46.   }
  47. }
  48. int Heap::remove() {
  49.   if (n == 0)
  50.     exit(1);
  51.   int temp = arr[0];
  52.   arr[0] = arr[--n];
  53.   heapDown(0);
  54.   arr[n] = 0;
  55.   return temp;
  56. }
  57. void Heap::heapDown(int i) {
  58.   int l = left(i);
  59.   int r = right(i);
  60.   // comparing parent to left/right child
  61.   // each has an inner if to handle if the first swap causes a second swap
  62.   //  ie    1   ->   3   ->   5
  63.   //      3   5    1   5    1   3
  64.   if (l < n && arr[i] < arr[l]) {
  65.     swap(arr[i], arr[l]);
  66.     heapDown(l);
  67.     if (r < n && arr[i] < arr[r]) {
  68.       swap(arr[i], arr[r]);
  69.       heapDown(r);
  70.     }
  71.   } else if (r < n && arr[i] < arr[r]) {
  72.     swap(arr[i], arr[r]);
  73.     heapDown(r);
  74.     if (l < n && arr[i] < arr[l]) {
  75.       swap(arr[i], arr[l]);
  76.       heapDown(l);
  77.     }
  78.   }
  79. }
  80. void Heap::print() {
  81.   for (int i = 0; i < n; i++) {
  82.     cout << arr[i] << " ";
  83.   }
  84.   cout << endl;
  85. }
  86. // adding a print inside since the sort itself destroys size incrementor
  87. void Heap::sort() {
  88.   int temp = n;
  89.   while (n > 1) {
  90.     swap(arr[--n], arr[0]);
  91.     heapDown(0);
  92.   }
  93.   for (int i = 0; i < temp; i++) {
  94.     cout << arr[i] << " ";
  95.   }
  96.   cout << endl;
  97. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin 
Standard input is empty
compilation info 
prog.cpp:1:9: warning: #pragma once in main file [enabled by default]
 #pragma once
         ^
prog.cpp:31:18: fatal error: Heap.h: No such file or directory
 #include "Heap.h"
                  ^
compilation terminated.
stdout 
Standard output is empty
https://ideone.com/PPh4eQ
language:
C++14 (gcc 8.3)
created:
10 years 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!