fork download
copy 
  1. // C++ Program for Implementing Max Heap
  2. #include <iostream>
  3. #include <vector>
  4. #include <climits>
  5.  
  6. using namespace std;
  7.  
  8. // Template for MaxHeap
  9. template <typename T>
  10. // Class for MaxHeap
  11. class MaxHeap {
  12. private:
  13.     vector<T> array;  
  14.     int size;
  15.     int capacity;     
  16.  
  17. public:
  18.     // Constructor to initialize the heap with a given capacity
  19.      MaxHeap(int capacity) {
  20.         this->size = 0;
  21.         this->capacity = capacity;
  22.         this->array.resize(capacity);
  23.     }
  24.  
  25.     // Function to heapify the node at index i
  26.     void heapify(int i) {
  27.         int largest = i;           
  28.         int left = 2 * i + 1;      
  29.         int right = 2 * i + 2;     
  30.  
  31.         if (left < size && array[left] > array[largest])
  32.             largest = left;
  33.  
  34.  
  35.         if (right < size && array[right] > array[largest])
  36.             largest = right;
  37.  
  38.  
  39.         if (largest != i) {
  40.             swap(array[i], array[largest]);  
  41.             heapify(largest);               
  42.         }
  43.     }
  44.  
  45.     // Function to build a max heap from a given array
  46.     void buildHeap(const vector<T>& arr) {
  47.         capacity = arr.size();
  48.         size = capacity;
  49.         array = arr;
  50.  
  51.         // Build heap (rearrange array)
  52.         for (int i = (size - 1) / 2; i >= 0; i--) {
  53.             heapify(i);
  54.         }
  55.     }
  56.  
  57.     // Function to insert a new value into the heap
  58.     void insert(T value) {
  59.         if (size == capacity) {
  60.             // Resize the heap if necessary
  61.             capacity *= 2;
  62.             array.resize(capacity);
  63.         }
  64.  
  65.         size++;
  66.         int i = size - 1;
  67.         array[i] = value;
  68.  
  69.         // Fix the max heap property if it is violated
  70.         while (i != 0 && array[(i - 1) / 2] < array[i]) {
  71.             swap(array[i], array[(i - 1) / 2]);
  72.             i = (i - 1) / 2;
  73.         }
  74.     }
  75.  
  76.   // Function to get the value of the root node of the max heap
  77.     T top() {
  78.         if (size <= 0)
  79.         // Indicates that the heap is empty
  80.             return -1; 
  81.  
  82.         return array[0];
  83.     }
  84.  
  85.     // Function to remove and return the maximum value from the heap
  86.     T pop() {
  87.         if (size <= 0)
  88.             return -1; 
  89.         if (size == 1) {
  90.             size--;
  91.             return array[0];
  92.         }
  93.  
  94.         // Store the maximum value, and remove it
  95.         T root = array[0];
  96.         array[0] = array[size - 1];
  97.         size--;
  98.         // Heapify the root node after deletion
  99.         heapify(0);  
  100.         return root;
  101.     }
  102.  
  103.     // Function to delete a specific key from the heap
  104.     void deleteKey(T key) {
  105.         // Find the index of the key
  106.         int index = -1;
  107.         for (int i = 0; i < size; ++i) {
  108.             if (array[i] == key) {
  109.                 index = i;
  110.                 break;
  111.             }
  112.         }
  113.         // If key is not found, return
  114.         if (index == -1) {
  115.             cout << "Key not found" << endl;
  116.             return;
  117.         }
  118.  
  119.         // If the key is found, delete it
  120.         // If it's the last element, simply reduce the size
  121.         if (index == size - 1) {
  122.             size--;
  123.             return;
  124.         }
  125.  
  126.         // Move the last element to the index of the key to be deleted
  127.         array[index] = array[size - 1];
  128.         size--;
  129.  
  130.         // Heapify down to maintain heap property
  131.         heapify(index);
  132.     }
  133.  
  134.     // Function to print the heap
  135.     void print() const {
  136.         cout << "Max Heap: ";
  137.         for (int i = 0; i < size; ++i)
  138.             cout << array[i] << " ";
  139.         cout << endl;
  140.     }
  141. };
  142.  
  143. int main() {
  144.     // Create a MaxHeap with initial capacity of 6
  145.     MaxHeap<int> maxHeap(10);
  146.     vector<int> arr = {91, 84, 66, 53, 48, 2, 24, 19, 7, 13};
  147.  
  148.     // Build the heap from the array
  149.     maxHeap.buildHeap(arr);
  150.  
  151.     // Print the max heap
  152.     maxHeap.print();
  153.  
  154.     // Insert a node into the heap
  155.     // maxHeap.insert(9);
  156.     // cout << "After inserting 9: " << endl;
  157.     // maxHeap.print();
  158.  
  159.     // Get the maximum value from the max heap
  160.     cout << "Top value: " << maxHeap.top() << endl;
  161.  
  162.     // Delete the root node of the max heap
  163.     cout << "Popped value: " << maxHeap.pop() << endl;
  164.     cout << "After popping: ";
  165.     maxHeap.print();
  166.  
  167.     // Delete a specific value from the max heap
  168.     maxHeap.deleteKey(5);
  169.     cout << "After deleting the node 5: ";
  170.     maxHeap.print();
  171.  
  172.     return 0;
  173. }
  174.  
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
2
3 5
stdout
copy 
Max Heap: 91 84 66 53 48 2 24 19 7 13 
Top value: 91
Popped value: 91
After popping: Max Heap: 84 53 66 19 48 2 24 13 7 
Key not found
After deleting the node 5: Max Heap: 84 53 66 19 48 2 24 13 7
https://ideone.com/GGyXBu
language:
C++ (gcc 8.3)
created:
10 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!