I made my custom heap, that allow to change and delete elements.
Please review it and tell me about any found bugs: https://bitbucket.org/nshatokhin/priorityqueue/src/master/
Is this implementation optimal? Is any better implementations exist?
```c++
#pragma once
#include <cassert>
#include <cstdint>
#include <memory>
template<typename ObjectType, typename IdxType = uint32_t>
class PriorityQueue
{
public:
PriorityQueue(IdxType maxElements, ObjectType minusInfiniy, ObjectType plusInfinity) :
m_heapSize(0), m_maxSize(maxElements), m_minusInfinity(minusInfiniy), m_plusInfinity(plusInfinity)
{
assert(maxElements > 0);
m_objects = new ObjectType[m_maxSize];
m_externalIndices = new IdxType[maxElements];
m_internalIndices = new IdxType[maxElements];
for (IdxType i = 0; i < maxElements; i++)
{
m_externalIndices[i] = i;
m_internalIndices[i] = i;
}
}
~PriorityQueue()
{
delete[] m_objects;
delete[] m_externalIndices;
delete[] m_internalIndices;
}
IdxType heapSize() const
{
return m_heapSize;
}
ObjectType * objects()
{
return m_objects;
}
IdxType * indices()
{
return m_externalIndices;
}
IdxType * buildHeap(ObjectType * array, IdxType elementsCount)
{
assert(elementsCount <= m_maxSize);
std::memcpy(m_objects, array, sizeof(ObjectType)*elementsCount);
m_heapSize = elementsCount;
for (IdxType i = 0; i <= m_heapSize / 2; i++)
{
siftDown(m_heapSize / 2 - i);
}
return m_externalIndices;
}
ObjectType min()
{
if (m_heapSize == 0)
return m_plusInfinity;
return m_objects[0];
}
ObjectType extractMin()
{
if (m_heapSize == 0)
return m_plusInfinity;
ObjectType min = m_objects[0];
if (m_heapSize - 1 != 0)
{
exchangeObjects(0, m_heapSize - 1);
}
m_heapSize--;
siftDown(0);
return min;
}
IdxType insert(const ObjectType &obj)
{
assert(m_heapSize < m_maxSize);
m_heapSize++;
IdxType index = m_externalIndices[m_heapSize - 1];
m_objects[m_heapSize - 1] = obj;
siftUp(m_heapSize - 1);
return index;
}
void update(IdxType i, const ObjectType &obj)
{
assert(i < m_maxSize && m_internalIndices[i] < m_heapSize);
ObjectType &old = m_objects[m_internalIndices[i]];
if (old < obj)
{
old = obj;
siftDown(0);
}
else if (old > obj)
{
old = obj;
siftUp(m_internalIndices[i]);
}
}
void remove(IdxType i)
{
update(i, m_minusInfinity);
extractMin();
}
protected:
void exchangeObjects(IdxType obj1, IdxType obj2)
{
ObjectType tempObj = m_objects[obj1];
m_objects[obj1] = m_objects[obj2];
m_objects[obj2] = tempObj;
IdxType tempIdx = m_internalIndices[m_externalIndices[obj1]];
m_internalIndices[m_externalIndices[obj1]] = m_internalIndices[m_externalIndices[obj2]];
m_internalIndices[m_externalIndices[obj2]] = tempIdx;
tempIdx = m_externalIndices[obj1];
m_externalIndices[obj1] = m_externalIndices[obj2];
m_externalIndices[obj2] = tempIdx;
}
void siftDown(IdxType i)
{
IdxType left, right, j;
while (2 * i + 1 < m_heapSize)
{
left = 2 * i + 1;
right = 2 * i + 2;
j = left;
if (right < m_heapSize && m_objects[right] < m_objects[left])
{
j = right;
}
if (m_objects[i] <= m_objects[j])
{
break;
}
exchangeObjects(i, j);
i = j;
}
}
void siftUp(IdxType i)
{
IdxType parent = (i - 1) / 2;
while (i > 0 && m_objects[i] < m_objects[parent])
{
exchangeObjects(i, parent);
i = parent;
parent = (i - 1) / 2;
}
}
protected:
uint32_t m_heapSize, m_maxSize;
ObjectType * m_objects;
IdxType * m_externalIndices, * m_internalIndices;
ObjectType m_minusInfinity, m_plusInfinity;
};
```