template <typename T>
class Array
{
public:
Array(const size_t capasity) : _size(0), _capacity(capasity) {}
int Size() const
{
return _size;
}
bool IsEmpty() const
{
return _size == 0;
}
virtual void Pop() = 0;
protected:
size_t _size, _capacity;
virtual void PushWithResize(const T& item) = 0;
};
template <typename T>
class PriotrityQueue : public Array<T>
{
public:
PriotrityQueue() : Array<T>(1), _node(new Node[_capacity]), _level(0) {}
~PriotrityQueue()
{
delete[] _node;
}
struct Node
{
T Data;
unsigned int Priority;
Node():Data(T{}),Priority(int{}) {}
Node(const T& data, const unsigned int priority) :Data(data), Priority(priority) {}
};
void Push(const T& item, int priority)
{
int size = _size + 1;
Node node(item, priority);
if (size > _capacity)
{
PushWithResize(item);
TrySort(node, _size, _level);
}
else if (size > 1)
{
TrySort(node, _size, _level);
}
else if (size == 1)
{
_node[_size] = node;
}
_size = size;
}
void Pop() override
{
}
T& Top()
{
return _node;
}
private:
using Array<T>::_size;
using Array<T>::_capacity;
Node* _node;
int _level;
void PushWithResize(const T& item) override
{
_capacity = _capacity - 1 == 0 ? 3 : (_capacity - 1) * 2 + 1;
_level++;
auto node = new Node[_capacity];
for (int index = 0; index < _size; index++)
{
node[index] = _node[index];
}
delete[] _node;
_node = node;
}
void TrySort(Node& node, int currentIndex, int currentLevel)
{
int level = currentLevel, maxItemsOnLevel = 1 << level;
int position = currentIndex + 1 - maxItemsOnLevel, parentPosition = position / 2;
auto GetIndex = [](int position, int level)
{
int index = 0;
for (int curLvl = 0; curLvl < level; curLvl++)
{
index += 1 << curLvl;
}
return index + position;
};
int parentIndex = GetIndex(parentPosition, level - 1);
if (node.Priority > _node[parentIndex])
{
_node[currentIndex] = _node[parentIndex];
_node[parentIndex] = node;
if (parentIndex != 0)
{
TrySort(node, parentIndex, level - 1);
}
}
else if(level == _level)
{
_node[_size] = node;
}
}
};