PrioQueue.cpp

#include "PrioQueue.h"

PrioQueue::PrioQueue(int maxCapacity) : size(0), capacity(maxCapacity) {
    heap = new Node[maxCapacity];
}

PrioQueue::~PrioQueue() {
    delete[] heap;
}

void PrioQueue::swap(Node &a, Node &b) {
    Node temp = a;
    a = b;
    b = temp;
}

void PrioQueue::heapUp(int index) {
    while (index > 0) {
        int parent = (index - 1) / 2;
        if (heap[parent].time <= heap[index].time) break;
        swap(heap[parent], heap[index]);
        index = parent;
    }
}

void PrioQueue::heapDown(int index) {
    while (true) {
        int left = 2 * index + 1;
        int right = 2 * index + 2;
        int smallest = index;

        if (left < size && heap[left].time < heap[smallest].time) smallest = left;
        if (right < size && heap[right].time < heap[smallest].time) smallest = right;

        if (smallest == index) break;
        swap(heap[index], heap[smallest]);
        index = smallest;
    }
}

void PrioQueue::push(Node node) {
    if (size >= capacity) {
        capacity *= 2;
        Node* newHeap = new Node[capacity];
        for (int i = 0; i < size; ++i) {
            newHeap[i] = heap[i];
        }
        delete[] heap;
        heap = newHeap;
    }
    heap[size] = node;
    heapUp(size);
    size++;
}

Node PrioQueue::pop() {
    Node top = heap[0];
    heap[0] = heap[--size];
    heapDown(0);
    return top;
}

bool PrioQueue::isEmpty() const {
    return size == 0;
}