daily pastebin goal
15%
SHARE
TWEET

Untitled

a guest Feb 17th, 2017 59 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #ifndef HEAP_PRIORITY_QUEUE_H
  2. #define HEAP_PRIORITY_QUEUE_H
  3.  
  4. #include "IPriorityQueue.h"
  5.  
  6. #include <iostream>
  7. #include <vector>
  8. #include <functional>
  9.  
  10. template<class K, class V> class HeapPriorityQueue : public IPriorityQueue < K, V > {
  11. private:
  12.     std::vector<Entry<K, V>> entries;
  13.     std::function<int(K, K)> compareFunction;
  14.  
  15.     // ------------------------------
  16.  
  17.     void upheap(unsigned int currentEntryIndex) {
  18.         while (currentEntryIndex > 0) {
  19.             int parentEntryIndex = indexOfParent(currentEntryIndex);
  20.  
  21.             Entry<K, V> parent = entries.at(parentEntryIndex);
  22.             K parentKey = parent.getKey();
  23.  
  24.             Entry<K, V> current = entries.at(currentEntryIndex);
  25.             K currentKey = current.getKey();
  26.  
  27.             if (compareFunction(parentKey, currentKey) > 0) {
  28.                 swap(parentEntryIndex, currentEntryIndex);
  29.                 currentEntryIndex = parentEntryIndex;
  30.             }
  31.             else {
  32.                 return;
  33.             }
  34.         }
  35.     }
  36.  
  37.     void downheap(unsigned int currentEntryIndex) {
  38.         while (currentEntryIndex < entries.size() - 1) {
  39.             bool hasLeft = hasLeftEntry(currentEntryIndex);
  40.             bool hasRight = hasRightEntry(currentEntryIndex);
  41.             int leftIndex = indexOfLeft(currentEntryIndex);
  42.             int rightIndex = indexOfRight(currentEntryIndex);
  43.  
  44.             unsigned int smallestBelowIndex = -1;
  45.  
  46.             if (hasLeft) {
  47.                 smallestBelowIndex = leftIndex;
  48.             }
  49.             else { break; }
  50.  
  51.             if (hasRight) {
  52.                 // If leftKey is bigger than rightKey
  53.                 if (compareFunction(entries.at(leftIndex).getKey(), entries.at(rightIndex).getKey()) > 0) {
  54.                     smallestBelowIndex = rightIndex;
  55.                 }
  56.             }
  57.  
  58.             // --------------------------------
  59.             // if the smallest below is smaller than current -> swap + update i
  60.             if (smallestBelowIndex != -1) {
  61.                 K currentKey = entries.at(currentEntryIndex).getKey();
  62.                 K smallestKey = entries.at(smallestBelowIndex).getKey();
  63.                 if (compareFunction(currentKey, smallestKey) > 0) {
  64.                     swap(currentEntryIndex, smallestBelowIndex);
  65.                     currentEntryIndex = smallestBelowIndex;
  66.                 }
  67.             }
  68.             else { break; }
  69.         }
  70.     }
  71.  
  72.     unsigned int indexOfParent(unsigned int i) {
  73.         return (i - 1) / 2;
  74.     }
  75.  
  76.     unsigned int indexOfLeft(unsigned int i) {
  77.         return i * 2 + 1;
  78.     }
  79.  
  80.     unsigned int indexOfRight(unsigned int i) {
  81.         return i * 2 + 2;
  82.     }
  83.  
  84.     bool hasLeftEntry(unsigned int i) {
  85.         return this->indexOfLeft(i) < entries.size();
  86.     }
  87.  
  88.     bool hasRightEntry(unsigned int i) {
  89.         return this->indexOfRight(i) < entries.size();
  90.     }
  91.  
  92.     void swap(unsigned int i, unsigned int j) {
  93.         if (i >= entries.size() || j >= entries.size()) {
  94.             std::cerr << "swap(i, j) :: Invalid arguments!";
  95.         }
  96.  
  97.         iter_swap(entries.begin() + i, entries.begin() + j);
  98.     }
  99.  
  100. public:
  101.     HeapPriorityQueue<K, V>(std::function<int(K, K)> compareFunction) {
  102.         entries = std::vector<Entry<K, V>>();
  103.         this->compareFunction = compareFunction;
  104.     }
  105.  
  106.     unsigned int size() override {
  107.         return entries.size();
  108.     }
  109.  
  110.     bool isEmpty() override {
  111.         return this->size() == 0;
  112.     };
  113.  
  114.     Entry<K, V> * insert(K key, V value) override {
  115.         Entry<K, V> newEntry = Entry<K, V>(key, value);
  116.         entries.push_back(newEntry);
  117.         this->upheap(entries.size() - 1);
  118.  
  119.         return &newEntry;
  120.     }
  121.  
  122.     Entry<K, V> * min() override {
  123.         return (!isEmpty()) ? &entries.at(0) : NULL;
  124.     }
  125.  
  126.     Entry<K, V> * removeMin() override {
  127.         if (isEmpty()) {
  128.             return NULL;
  129.         }
  130.  
  131.         Entry<K, V> removed = *(this->min());
  132.         this->swap(0, entries.size() - 1);
  133.         entries.erase(entries.end() - 1);
  134.         this->downheap(0);
  135.  
  136.         return &removed;
  137.     }
  138.  
  139.     // --------------- Utility ------------------
  140.  
  141.     void clear() {
  142.         entries = std::vector<Entry<K, V>>();
  143.     }
  144.  
  145.     void print() {
  146.         std::cout << "Priority queue content:" << std::endl;
  147.         for (Entry<K, V> entry : entries) {
  148.             std::cout << "[" << entry.getKey() << " -> " << entry.getValue() << "]" << std::endl;
  149.         }
  150.         std::cout << std::endl;
  151.     }
  152. };
  153.  
  154. #endif
RAW Paste Data
Top