priority_queue.hpp

 #ifndef priority_queue_H
#define priority_queue_H

#include "vector.hpp"
#include <functional>

template <typename T, typename Compare = std::greater<T>>
class priority_queue{
// left_child : 2i+1
// right_chile : 2i+2
// parent : (i-1)//2

private:
    vector<T> heap;
    Compare comp;

    void swap_and_update_arg1_to_arg2(int& pos1, int& pos2){
        T swap_ = heap[pos1];
        heap[pos1] = heap[pos2];
        heap[pos2] = swap_;

        pos1 = pos2;
    }

public:
    priority_queue(Compare c = Compare()) : comp(c){}

    ~priority_queue(){}

    priority_queue(const priority_queue& other){
        heap = other.heap;
    }

    priority_queue(priority_queue&& other) noexcept {
        if(&other!=this){
            this->heap = std::move(other.heap);
            vector<T> empty_vector;
            other.heap = empty_vector;
        }
    }

    priority_queue& operator=(const priority_queue& other){
        heap = other.heap;
        return *this;
    }

    priority_queue& operator=(priority_queue&& other){
        if(&other!=this){
            this->heap = std::move(other.heap);
            vector<T> empty_vector;
            other.heap = empty_vector;
        }
        return *this;
    }

    void push(T element){
        heap.push_back(element);
        
        int curr_index = heap.size()-1;

        while (curr_index > 0) {
            int parent_index = (curr_index - 1) / 2;
            if (comp(heap[curr_index], heap[parent_index])) {
                swap_and_update_arg1_to_arg2(curr_index, parent_index);
            } 
            else break;
        }
    }
    
    const T& top() const {
        if(heap.empty()) throw std::runtime_error("Tried to peek into an empty priority_queue: priority_queue.hpp\n");
        return heap[0];
    }

    T pop(){
        if(heap.empty()) throw std::runtime_error("Tried to pop an empty priority_queue: priority_queue.hpp\n");

        T popped_element = heap[0];
        heap[0] = heap[heap.size()-1];
        heap.pop_back();

        int curr_index = 0;
        while(curr_index<heap.size()){
            int child_left_index = (curr_index*2)+1;
            int child_right_index = (curr_index*2)+2;

            if(child_left_index<heap.size() && child_right_index<heap.size()){
                bool left_greater = comp(heap[child_left_index],heap[curr_index]);
                bool right_greater = comp(heap[child_right_index],heap[curr_index]);
                if(!left_greater && !right_greater){
                    break;
                }
                else if(left_greater && !right_greater){
                    swap_and_update_arg1_to_arg2(curr_index, child_left_index);
                }
                else if(right_greater && !left_greater){
                    swap_and_update_arg1_to_arg2(curr_index, child_right_index);
                }
                else{
                    if(comp(heap[child_left_index],heap[child_right_index])){
                        swap_and_update_arg1_to_arg2(curr_index, child_left_index);
                    }
                    else{
                        swap_and_update_arg1_to_arg2(curr_index, child_right_index);
                    }
                }
            }
            else if(child_left_index>=heap.size() && child_right_index>=heap.size()){
                break;
            }
            else{
                int child_index = (child_left_index>=heap.size()) ? child_right_index : child_left_index;

                bool child_greater = comp(heap[child_index],heap[curr_index]);
                if(child_greater){
                    swap_and_update_arg1_to_arg2(curr_index, child_index);
                }
                else{
                    break;
                }
            }
        }

        return popped_element;
    }

    bool empty() const {
        return heap.empty();
    }

    int size(){
        return heap.size();
    }
};

#endif