Anupznk

heap.h

Apr 8th, 2021
40
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 bubbleUpLoop(int index) {
  60. int parent = index;
  61. while(parent != 0) {
  62.  
  63. parent = getParentIndex(index);
  64. if (numbers[parent] < numbers[index]) {
  65. // THIS VIOLATES THE PROPERTY OF MAX HEAP
  66. swapNums(parent, index);
  67. index = parent;
  68. }
  69. }
  70. }
  71.  
  72. void insert(double number) {
  73. if (length == arraySize) {
  74. try{
  75. throw length;
  76. }
  77. catch(int ex) {
  78. cout<<"Exception: The Heap is Full"<<endl;
  79. }
  80. } else {
  81. numbers[length] = number;
  82. // INSERTING AT THE END OF THE ARRAY
  83. length++;
  84. // bubbleUp(length-1);
  85. bubbleUpLoop(length-1);
  86. }
  87. }
  88.  
  89. int getMax() {
  90. if (length > 0)
  91. return numbers[0];
  92. else {
  93. try{
  94. throw length;
  95. }
  96. catch(int ex) {
  97. cout<<"Exception: The Heap is empty. Garbage value alert"<<endl;
  98. }
  99. }
  100. }
  101.  
  102. int getLeftChild(int index) {
  103. return (index + 1) * 2 - 1;
  104. }
  105.  
  106. int getRightChild(int index) {
  107. return (index + 1) * 2;
  108. }
  109.  
  110. void heapify(int index) {
  111. int maxValIndex = index;
  112.  
  113. int leftChildIndex = getLeftChild(index);
  114. int rightChildIndex = getRightChild(index);
  115.  
  116.  
  117.  
  118. if (leftChildIndex < length && numbers[leftChildIndex] > numbers[maxValIndex]) {
  119. maxValIndex = leftChildIndex;
  120. }
  121. if (rightChildIndex < length && numbers[rightChildIndex] > numbers[maxValIndex]) {
  122. maxValIndex = rightChildIndex;
  123. }
  124.  
  125. if (maxValIndex != index) {
  126. swapNums(maxValIndex, index);
  127.  
  128. heapify(maxValIndex);
  129. }
  130. }
  131.  
  132. void deleteKey() {
  133. if (length == 0) {
  134. try{
  135. throw length;
  136. }
  137. catch(int ex) {
  138. cout<<"Exception: The Heap is empty. Cannot delete"<<endl;
  139. }
  140. } else{
  141. int lastNum = numbers[length - 1];
  142. numbers[0] = lastNum;
  143. length--;
  144.  
  145. heapify(0);
  146. }
  147. }
  148.  
  149. int size() {
  150. return length;
  151. }
  152.  
  153. int * getHeap() {
  154. return numbers;
  155. }
  156.  
  157. void setHeap(int * numbers) {
  158. this->numbers = numbers;
  159. }
  160.  
  161. ~Heap() {
  162. delete [] numbers;
  163.  
  164. }
  165.  
  166. };
  167.  
  168. void heapsort(vector<int>&v) {
  169. Heap newHeap(v.size());
  170.  
  171. for(int i = 0; i < v.size(); i++)
  172. newHeap.insert(v[i]);
  173.  
  174. v.clear();
  175.  
  176. for (int i = 0; newHeap.size(); i--) {
  177. v.push_back(newHeap.getMax());
  178. newHeap.deleteKey();
  179. }
  180.  
  181. cout<<"Random number for debugging: " <<v[1232]<< endl;
  182. }
  183.  
  184. #endif
  185.  
RAW Paste Data