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.     void heapifyUp(int child_pos) {
  36.         int parent_pos = parent(child_pos);
  37.         if (child_pos == 0 || parent_pos == -1 || arr[parent_pos] < arr[child_pos]) {
  38.             return;
  39.         }
  40.         swap(arr[parent_pos], arr[child_pos]);
  41.         heapifyUp(parent_pos);
  42.     }
  43.  
  44.     void push(int node) {
  45.         assert(!isFull());
  46.         arr[size++] = node;
  47.         heapifyUp(size - 1);
  48.     }
  49.  
  50.     void heapifyDown(int parent_pos) {
  51.         int left_child = leftchild(parent_pos);
  52.         int right_child = rightchild(parent_pos);
  53.         int min_child = parent_pos;
  54.  
  55.         if (left_child != -1 && arr[left_child] < arr[min_child]) {
  56.             min_child = left_child;
  57.         }
  58.  
  59.         if (right_child != -1 && arr[right_child] < arr[min_child]) {
  60.             min_child = right_child;
  61.         }
  62.  
  63.         if (min_child != parent_pos) {
  64.             swap(arr[parent_pos], arr[min_child]);
  65.             heapifyDown(min_child);
  66.         }
  67.     }
  68.  
  69.     void pop() {
  70.         assert(!isEmpty());
  71.         swap(arr[0], arr[--size]);
  72.         heapifyDown(0);
  73.     }
  74.  
  75.     int top() {
  76.         assert(!isEmpty());
  77.         return arr[0];
  78.     }
  79.  
  80.     bool isEmpty() {
  81.         return size == 0;
  82.     }
  83.  
  84.     bool isFull() {
  85.         return size == capacity;
  86.     }
  87.  
  88.     //Problem 5:
  89.     void heapSort(int *a, int size){
  90.         MinHeap heap;
  91.         for(int i = 0; i < size;i++){
  92.             heap.push(a[i]);
  93.         }
  94.         for(int i = 0; i <size; i++){
  95.             a[i] = heap.top();
  96.             heap.pop();
  97.         }
  98.     }
  99. };
  100. int main(){
  101.     MinHeap h; 
  102.     int vec[]{1, 3, 5, 7, 9, 6, 8};
  103.     h.heapSort(vec,7);
  104.     cout << "The heap sort is : \n";
  105.     for(auto value : vec){
  106.         cout << value << " ";
  107.     }
  108.     return 0;
  109. }
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
The heap sort is : 
1 3 5 6 7 8 9
https://ideone.com/GuI8ge
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!