fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. void printMinHeap(vector<int> arr) {
  5.     for (int i = 0; i < arr.size(); i++) {
  6.         cout << arr[i] << " ";    
  7.     }
  8.     cout << endl;
  9. }
  10.  
  11. int getLeftChildIndex(int parentIndex) {
  12.     return parentIndex * 2 + 1;
  13. }
  14.  
  15. int getRightChildIndex(int parentIndex) {
  16.     return parentIndex * 2 + 2;
  17. }
  18.  
  19. int getParentIndex(int childIndex) {
  20.     return  (childIndex - 1) / 2;
  21. }
  22.  
  23. void heapifyUp(vector<int> &arr, int index) {
  24.     int parentIndex = getParentIndex(index);
  25.     while (parentIndex >= 0 && arr[index] < arr[parentIndex]) {
  26.         swap(arr[parentIndex], arr[index]);
  27.         index = parentIndex;
  28.         parentIndex = getParentIndex(index);
  29.     }
  30. }
  31.  
  32. void heapifyDown(vector<int> &arr, int parentIndex) {
  33.     int leftChildIndex = getLeftChildIndex(parentIndex);  
  34.     int smallerChildIndex;    
  35.     while (leftChildIndex < arr.size()) {
  36.         // we need to find out which is smaller
  37.         // left child or right child.
  38.         smallerChildIndex = leftChildIndex;
  39.         int rightChildIndex = getRightChildIndex(parentIndex);
  40.         if (rightChildIndex < arr.size() &&
  41.             arr[rightChildIndex] < arr[smallerChildIndex]) {
  42.             smallerChildIndex = rightChildIndex;        
  43.         }
  44.         if (arr[parentIndex] < arr[smallerChildIndex]) {
  45.             // this condition implies, min-heap integrity is
  46.             // already maintained.    
  47.             break;
  48.         }
  49.         swap(arr[parentIndex], arr[smallerChildIndex]);
  50.         parentIndex = smallerChildIndex;
  51.         leftChildIndex = getLeftChildIndex(parentIndex);
  52.     }
  53. }
  54.  
  55.  
  56. void createMinHeap(vector<int> &arr) {
  57.     int n = arr.size();
  58.     for (int i = n / 2 - 1; i >= 0; i--) {
  59.         heapifyDown(arr, i);    
  60.     }
  61. }
  62.  
  63.  
  64. void addElement(vector<int> &arr, int newEle) {
  65.     arr.push_back(newEle);
  66.     heapifyUp(arr, arr.size() - 1);
  67. }
  68.  
  69.  
  70. void removeElement(vector<int> &arr) {
  71.     int n = arr.size();
  72.     swap(arr[n - 1], arr[0]);
  73.     arr.pop_back();
  74.     heapifyDown(arr, 0);
  75. }
  76.  
  77.  
  78. int main() {
  79.     vector<int> arr = {10, 22, 32, 6, 25, 22, 15, 56, 65, 72};
  80.     createMinHeap(arr);
  81.     printMinHeap(arr);
  82.     addElement(arr, 8);
  83.     printMinHeap(arr);
  84.     removeElement(arr);
  85.     printMinHeap(arr);
  86.     removeElement(arr);
  87.     printMinHeap(arr);
  88. }
  89.  
Success #stdin #stdout 0.01s 5512KB
comments (?)
stdin 
Standard input is empty
stdout 
6 10 15 22 25 22 32 56 65 72 
6 8 15 22 10 22 32 56 65 72 25 
8 10 15 22 25 22 32 56 65 72 
10 22 15 56 25 22 32 72 65
https://ideone.com/b2dYYF
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
secret

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!