Anupznk

heap.h

May 30th, 2021
704
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //
  2. // Created by Anup Bhowmik on 4/6/2021.
  3. //
  4. #include<cstdlib>
  5. #include<vector>
  6. #include<iostream>
  7.  
  8. using namespace std;
  9.  
  10. #ifndef MYHEAP_HEAP_H
  11.  
  12. class Heap {
  13. private:
  14.  
  15.     int *numbers;
  16.     int length;
  17.     int arraySize;
  18.     int DEFAULT_SIZE = 1000;
  19.  
  20. public:
  21.  
  22.     Heap() {
  23.         numbers = new int[DEFAULT_SIZE];
  24.         arraySize = DEFAULT_SIZE;
  25.         length = 0;
  26.     }
  27.  
  28.     Heap(int size) {
  29.         numbers = new int[size];
  30.         arraySize = size;
  31.         length = 0;
  32.     }
  33.  
  34.     int getParentIndex(int index) {
  35.         return (index-1)/2;
  36.     }
  37.  
  38.     void swapNums(int firstIndex, int secondIndex) {
  39.         int temp;
  40.         temp = numbers[firstIndex];
  41.         numbers[firstIndex] = numbers[secondIndex];
  42.         numbers[secondIndex] = temp;
  43.     }
  44.  
  45.     void bubbleUp(int index) {
  46.         int parent;
  47.         if (index == 0)
  48.             return;
  49.         else {
  50.             parent = getParentIndex(index);
  51.             if (numbers[parent] < numbers[index]) {
  52.                 //  THIS VIOLATES THE PROPERTY OF MAX HEAP
  53.                 swapNums(parent, index);
  54.                 bubbleUp(parent);
  55.             }
  56.         }
  57.     }
  58.  
  59.     void insert(double number) {
  60.         if (length == arraySize) {
  61.             try{
  62.                 throw length;
  63.             }
  64.             catch(int ex) {
  65.                 cout<<"Exception: The Heap is Full"<<endl;
  66.             }
  67.         } else {
  68.             numbers[length] = number;
  69.             //  INSERTING AT THE END OF THE ARRAY
  70.             length++;
  71.             bubbleUp(length-1);
  72.         }
  73.     }
  74.  
  75.     int getMax() {
  76.         if (length > 0)
  77.             return numbers[0];
  78.         else {
  79.             try{
  80.                 throw length;
  81.             }
  82.             catch(int ex) {
  83.                 cout<<"Exception: The Heap is empty. Garbage value alert"<<endl;
  84.             }
  85.         }
  86.     }
  87.  
  88.     int getLeftChild(int index) {
  89.         return (index + 1) * 2 - 1;
  90.     }
  91.  
  92.     int getRightChild(int index) {
  93.         return (index + 1) * 2;
  94.     }
  95.  
  96.     void heapify(int index) {
  97.         int maxValIndex = index;
  98.  
  99.         int leftChildIndex = getLeftChild(index);
  100.         int rightChildIndex = getRightChild(index);
  101.  
  102.  
  103.  
  104.         if (leftChildIndex < length && numbers[leftChildIndex] > numbers[maxValIndex]) {
  105.             maxValIndex = leftChildIndex;
  106.         }
  107.         if (rightChildIndex < length && numbers[rightChildIndex] > numbers[maxValIndex]) {
  108.             maxValIndex = rightChildIndex;
  109.         }
  110.  
  111.         if (maxValIndex != index) {
  112.             swapNums(maxValIndex, index);
  113.  
  114.             heapify(maxValIndex);
  115.         }
  116.     }
  117.  
  118.     void deleteKey() {
  119.         if (length == 0) {
  120.             try{
  121.                 throw length;
  122.             }
  123.             catch(int ex) {
  124.                 cout<<"Exception: The Heap is empty. Cannot delete"<<endl;
  125.             }
  126.         } else{
  127.             int lastNum = numbers[length - 1];
  128.             numbers[0] = lastNum;
  129.             length--;
  130.  
  131.             heapify(0);
  132.         }
  133.     }
  134.  
  135.     int size() {
  136.         return length;
  137.     }
  138.  
  139.     int * getHeap() {
  140.         return numbers;
  141.     }
  142.  
  143.     void setHeap(int * numbers) {
  144.         this->numbers = numbers;
  145.     }
  146.  
  147.     ~Heap() {
  148.         delete [] numbers;
  149.  
  150.     }
  151.  
  152. };
  153.  
  154.  void heapsort(vector<int>&v) {
  155.     Heap newHeap(v.size());
  156.  
  157.     for(int i = 0; i < v.size(); i++)
  158.         newHeap.insert(v[i]);
  159.  
  160.     v.clear();
  161.  
  162.     for (int i = 0;  newHeap.size(); i--) {
  163.         v.push_back(newHeap.getMax());
  164.         newHeap.deleteKey();
  165.     }
  166.  }
  167.  
  168. #endif
  169.  
RAW Paste Data