SHARE
TWEET

Untitled

a guest Sep 16th, 2019 81 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<iostream>
  2. #include<climits>
  3. using namespace std;
  4.  
  5. // Prototype of a utility function to swap two integers
  6. void swap(int *x, int *y);
  7.  
  8. // A class for Min Heap
  9. class MinHeap
  10. {
  11.     int *harr; // pointer to array of elements in heap
  12.     int capacity; // maximum possible size of min heap
  13.     int heap_size; // Current number of elements in min heap
  14.   public:
  15.     // Constructor
  16.     MinHeap(int capacity);
  17.  
  18.     // to heapify a subtree with the root at given index
  19.     void MinHeapify(int );
  20.  
  21.     int parent(int i) { return (i-1)/2; }
  22.  
  23.     // to get index of left child of node at index i
  24.     int left(int i) { return (2*i + 1); }
  25.  
  26.     // to get index of right child of node at index i
  27.     int right(int i) { return (2*i + 2); }
  28.  
  29.     // to extract the root which is the minimum element
  30.     int extractMin();
  31.  
  32.     // Decreases key value of key at index i to new_val
  33.     void decreaseKey(int i, int new_val);
  34.  
  35.     // Returns the minimum key (key at root) from min heap
  36.     int getMin() { return harr[0]; }
  37.  
  38.     // Deletes a key stored at index i
  39.     void deleteKey(int i);
  40.  
  41.     // Inserts a new key 'k'
  42.     void insertKey(int k);
  43. };
  44.  
  45. // Constructor: Builds a heap from a given array a[] of given size
  46. MinHeap::MinHeap(int cap)
  47. {
  48.     heap_size = 0;
  49.     capacity = cap;
  50.     harr = new int[cap];
  51. }
  52.  
  53. // Inserts a new key 'k'
  54. void MinHeap::insertKey(int k)
  55. {
  56.     if (heap_size == capacity)
  57.     {
  58.         cout << "\nOverflow: Could not insertKey\n";
  59.         return;
  60.     }
  61.  
  62.     // First insert the new key at the end
  63.     heap_size++;
  64.     int i = heap_size - 1;
  65.     harr[i] = k;
  66.  
  67.     // Fix the min heap property if it is violated
  68.     while (i != 0 && harr[parent(i)] > harr[i])
  69.     {
  70.     swap(&harr[i], &harr[parent(i)]);
  71.     i = parent(i);
  72.     }
  73. }
  74.  
  75. // Decreases value of key at index 'i' to new_val. It is assumed that
  76. // new_val is smaller than harr[i].
  77. void MinHeap::decreaseKey(int i, int new_val)
  78. {
  79.     harr[i] = new_val;
  80.     while (i != 0 && harr[parent(i)] > harr[i])
  81.     {
  82.     swap(&harr[i], &harr[parent(i)]);
  83.     i = parent(i);
  84.     }
  85. }
  86.  
  87. // Method to remove minimum element (or root) from min heap
  88. int MinHeap::extractMin()
  89. {
  90.     if (heap_size <= 0)
  91.         return INT_MAX;
  92.     if (heap_size == 1)
  93.     {
  94.         heap_size--;
  95.         return harr[0];
  96.     }
  97.  
  98.     // Store the minimum value, and remove it from heap
  99.     int root = harr[0];
  100.     harr[0] = harr[heap_size-1];
  101.     heap_size--;
  102.     MinHeapify(0);
  103.  
  104.     return root;
  105. }
  106.  
  107.  
  108. // This function deletes key at index i. It first reduced value to minus
  109. // infinite, then calls extractMin()
  110. void MinHeap::deleteKey(int i)
  111. {
  112.     decreaseKey(i, INT_MIN);
  113.     extractMin();
  114. }
  115.  
  116. // A recursive method to heapify a subtree with the root at given index
  117. // This method assumes that the subtrees are already heapified
  118. void MinHeap::MinHeapify(int i)
  119. {
  120.     int l = left(i);
  121.     int r = right(i);
  122.     int smallest = i;
  123.     if (l < heap_size && harr[l] < harr[i])
  124.         smallest = l;
  125.     if (r < heap_size && harr[r] < harr[smallest])
  126.         smallest = r;
  127.     if (smallest != i)
  128.     {
  129.         swap(&harr[i], &harr[smallest]);
  130.         MinHeapify(smallest);
  131.     }
  132. }
  133.  
  134. // A utility function to swap two elements
  135. void swap(int *x, int *y)
  136. {
  137.     int temp = *x;
  138.     *x = *y;
  139.     *y = temp;
  140. }
  141.  
  142. // Driver program to test above functions
  143. int main()
  144. {
  145.     MinHeap h(11);
  146.     h.insertKey(3);
  147.     h.insertKey(2);
  148.     h.deleteKey(1);
  149.     h.insertKey(15);
  150.     h.insertKey(5);
  151.     h.insertKey(4);
  152.     h.insertKey(45);
  153.     cout << h.extractMin() << " ";
  154.     cout << h.getMin() << " ";
  155.     h.decreaseKey(2, 1);
  156.     cout << h.getMin();
  157.   cout << endl;
  158.     return 0;
  159. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top