My implementation of binary heap

Question

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?

 #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;
 };

• Toby Speight: Could you summarise why you might use this in place of std::priority_queue? Is it the provision of element removal that's important?
• Robotex: priority_queue can't update and delete elements
• Robotex: D* lite needs object update and removal
• Joop Eggen: From binary heap to fibonacci heap is a (relatively) small step. Just an idea,
• Joop Eggen: The principle being instead of splitting in half, spltting size fib(n) into fib(n-2) and fib(n-1) and vice versa. Idea is better memory utilisation. Tricky too.

Answer 1

Missing <cstring> header (needed for std::memcpy()). Conversely, we've included <memory> but declined to take advantage of what it provides.

You have misspelt std::uint32_t (the template's default IdxType).

Using bare new[] instead of a vector gives a serious bug when a PriorityQueue is copied (use after free, and double delete). It's simpler and safer to use a std::vector to manage the arrays for us.

Giving external write access to the innards (objects(), indices()) allows outside code to break the object's invariants.

The buildHeap() member applies std::memcpy() without checking whether that's safe for ObjectType objects - we should be using std::move() (from <algorithm>) instead:

std::move(array, array+elementsCount, m_objects);

It's surprising that this method takes a pointer to array of mutable objects; we could consider an overload for const objects - that would use std::copy_n() rather than std::move():

 IdxType * buildHeap(ObjectType const* array, IdxType elementsCount)
 {
 assert(elementsCount <= m_maxSize);
 std::copy_n(array, elementsCount, m_objects);

Also in this method, don't use assert() for checking that needs to occur in production builds - that's a macro compiles to nothing when NDEBUG is defined. We wouldn't need that test if we were using a vector for storage.

Why are we writing our own heap algorithm instead of using std::make_heap() and related functions?

Object counts are best represented as std::size_t, not std::uint32_t. m_heapSize and m_maxSize ought to be of type IdxType.

• Robotex: Oh, I forgot copy constructor :)
• Robotex: > we should be using std::move() instead How to use it?
• Toby Speight: std::move(array, array+elementsCount, m_objects);. (Albeit, the ObjectType * array perhaps should be ObjectType const * array, and we'd use std::copy_n() in that case - I'll mention something about that).
• Robotex: Will std::move destroy original vector? I want to make copy of it, because many instances can use it for initialization Applied most of your comments: bitbucket.org/nshatokhin/priorityqueue
• Toby Speight: The raw pointers don't work well with copy construction or copy assignment; if you provide your own, then you'd also want to provide move constructor and move assignment. It's much simpler and safer to follow the Rule of Zero and delegate all that work to std::vector.