Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <utility>
- #include <vector>
- #include <stack>
- #include <algorithm>
- template <typename key_t, typename val_t>
- class Custom_QuickHeap {
- /*
- * @brief An implementation of QuickHeap data structure
- * see Gonzalo Navarro and Rodrigo Paredes - "Quickheaps: Simple, Efficient, and Cache-Oblivious"
- */
- public:
- Custom_QuickHeap(const size_t max_capacity);
- Custom_QuickHeap(const std::vector<std::pair<key_t, val_t>>& array, const size_t max_capacity);
- ~Custom_QuickHeap();
- void insert(const key_t& key, const val_t& value);
- std::pair<key_t, val_t> peakMin();
- std::pair<key_t, val_t> extractMin();
- void size();
- void dump();
- private:
- std::vector<std::pair<key_t, val_t>>* heap;
- std::stack<size_t>* pivots;
- size_t heap_begin;
- size_t capacity;
- size_t current_size;
- };
- template <typename key_t, typename val_t>
- Custom_QuickHeap<key_t, val_t>::Custom_QuickHeap(const size_t max_capacity) {
- /*
- * @brief constructor of an empty QuickHeap
- * @param max_capacity - maximal amount of elements in heap
- */
- capacity = max_capacity + 1; // + 1 is for artificial "+inf" pivot
- current_size = 0;
- heap = new std::vector<std::pair<key_t, val_t>>(capacity);
- pivots = new std::stack<size_t>;
- pivots->push(0);
- heap_begin = 0;
- }
- template <typename key_t, typename val_t>
- Custom_QuickHeap<key_t, val_t>::Custom_QuickHeap(const std::vector<std::pair<key_t, val_t>>& array,
- const size_t max_capacity) {
- /*
- * @brief constructor of a QuickHeap from an array;
- * @param array - array from which heap will be built
- * @param max_capacity - maximal amount of elements in heap
- */
- capacity = std::max(max_capacity, array.size()) + 1; // + 1 is for artificial "+inf" pivot
- current_size = array.size();
- heap = new std::vector<std::pair<key_t, val_t>>(capacity);
- pivots = new std::stack<size_t>;
- pivots->push(array.size());
- heap_begin = 0;
- for (size_t i = 0; i < array.size(); ++i) {
- heap->at(i) = array[i];
- }
- }
- int main() {
- std::cout << "Hello, World!" << std::endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement