SHARE
TWEET

heappqueue

a guest Feb 21st, 2020 84 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include "HeapPQueue.h"
  2. #include "Testing/HeapTests.h"
  3. #include "vector.h"
  4. using namespace std;
  5.  
  6. HeapPQueue::HeapPQueue() {
  7.     elems = new DataPoint[100];
  8.     allocatedSize = 100;
  9.     logicalSize = 0;
  10. }
  11.  
  12. HeapPQueue::~HeapPQueue() {
  13.     delete[] elems;
  14.  
  15. }
  16.  
  17. void HeapPQueue::grow() {
  18.     allocatedSize *= 2;
  19.  
  20.     DataPoint* newElems = new DataPoint[allocatedSize];
  21.  
  22.     for (int i = 0; i < logicalSize; i++) {
  23.         newElems[i] = elems[i];
  24.     }
  25.  
  26.     delete[] elems;
  27.     elems = newElems;
  28. }
  29.  
  30. void HeapPQueue::enqueue(const DataPoint& data) {
  31.  
  32.     if (logicalSize == allocatedSize) {
  33.         grow();
  34.     }
  35.     elems[logicalSize] = data;
  36.  
  37.     int numRows = determineRow(logicalSize+1);
  38.     logicalSize++;
  39.     int a = logicalSize;
  40.     for (int i = 0; i < numRows; i++){
  41.         int b = (a/2);
  42.         if (b != 0){
  43.             b--;
  44.         }
  45.         if (elems[b].weight > elems[a-1].weight){
  46.             DataPoint temp = elems[a-1];
  47.             elems[a-1] = elems[b];
  48.             elems[b] = temp;
  49.             a = b+1;
  50.         }
  51.  
  52.     }
  53. }
  54.  
  55. int HeapPQueue::size() const {
  56.     return logicalSize;
  57. }
  58.  
  59. DataPoint HeapPQueue::peek() const {
  60.     if (isEmpty()) {
  61.         error("You cannot peek at an empty queue");
  62.     }
  63.     return elems[0];
  64. }
  65.  
  66. DataPoint HeapPQueue::dequeue() {
  67.     if (isEmpty()) {
  68.         error("You cannot dequeue an empty queue");
  69.     }
  70.     int size = logicalSize;
  71.     DataPoint smallestValue = elems[0];
  72.     elems[0] = elems[size-1];
  73.     elems[size-1] = smallestValue;
  74.     logicalSize--;
  75.     int numRows = determineRow(logicalSize);
  76.     int j = 0;
  77.  
  78.     for (int i = 0; i < numRows-1; i++) {
  79.         int left = 2*j+1;
  80.         int right = 2*j+2;
  81.  
  82.  
  83.         if (logicalSize > right) {
  84.                 if (elems[left].weight >= elems[right].weight && (elems[j].weight > elems[right].weight)) {
  85.                     DataPoint tempValue = elems[j];
  86.                     elems[j] = elems[right];
  87.                     elems[right] = tempValue;
  88.                     j = right;
  89.                 }
  90.  
  91.                 else if (elems[j].weight > elems[left].weight){
  92.                     DataPoint tempValue = elems[j];
  93.                     elems[j] = elems[left];
  94.                     elems[left] = tempValue;
  95.                     j = left;
  96.                 }
  97.         }
  98.         else if ((logicalSize == right) && (elems[j].weight > elems[left].weight)) {
  99.             DataPoint tempValue = elems[j];
  100.             elems[j] = elems[left];
  101.             elems[left] = tempValue;
  102.             j = left;
  103.         }
  104.     }
  105.     logicalSize++;
  106.     DataPoint dequeuedElem = elems[logicalSize-1];
  107.     logicalSize--;
  108.     return dequeuedElem;
  109.  
  110. }
  111.  
  112. bool HeapPQueue::isEmpty() const {
  113.     return size() == 0;
  114. }
  115.  
  116. /* This function is purely for you to use during testing. You can have it do whatever
  117.  * you'd like, including nothing. We won't call this function during grading, so feel
  118.  * free to fill it with whatever is most useful to you!
  119.  *
  120.  * TODO: Delete this comment and replace it with one describing what this function
  121.  * actually does.
  122.  */
  123. void HeapPQueue::printDebugInfo() {
  124.     /* TODO: Delete this comment and (optionally) put debugging code here. */
  125. }
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