127 lines
2.5 KiB
C++
127 lines
2.5 KiB
C++
|
|
template <typename T> class heap
|
|
{
|
|
public:
|
|
T* data = NULL;
|
|
size_t n = 0, cap = 0;
|
|
|
|
public:
|
|
heap()
|
|
{
|
|
;
|
|
}
|
|
|
|
T pop()
|
|
{
|
|
// ENTER;
|
|
|
|
assert(this->n);
|
|
|
|
T retval = this->data[0], swap;
|
|
|
|
if (--n)
|
|
{
|
|
size_t l, r, smallest, i = 0;
|
|
|
|
data[0] = data[this->n];
|
|
|
|
again: l = 2 * i + 1, r = 2 * i + 2, smallest = i;
|
|
|
|
if (l < this->n && data[l] < data[i])
|
|
smallest = l;
|
|
|
|
if (r < this->n && data[r] < data[smallest])
|
|
smallest = r;
|
|
|
|
if (smallest != i)
|
|
{
|
|
swap = data[i];
|
|
data[i] = data[smallest];
|
|
data[smallest] = swap;
|
|
|
|
i = smallest;
|
|
|
|
goto again; // forgive my father for I have sinned.
|
|
}
|
|
}
|
|
|
|
// EXIT;
|
|
return retval;
|
|
}
|
|
|
|
void push(T pushme)
|
|
{
|
|
// ENTER;
|
|
|
|
if (n == cap)
|
|
{
|
|
cap = cap << 1 ?: 1;
|
|
|
|
if constexpr (std::is_trivially_copyable_v<T>)
|
|
{
|
|
data = realloc(data, sizeof(*data) * cap);
|
|
}
|
|
else
|
|
{
|
|
T* new_data = new T[cap]();
|
|
|
|
for (size_t i = 0; i < n; i++)
|
|
{
|
|
new_data[i] = std::move(data[i]);
|
|
}
|
|
|
|
delete[] data;
|
|
|
|
data = new_data;
|
|
}
|
|
}
|
|
|
|
size_t i = n++, j;
|
|
|
|
T swap;
|
|
|
|
data[i] = pushme;
|
|
|
|
for (; i > 0 && data[j = (i - 1) / 2] > data[i]; i = j)
|
|
{
|
|
swap = data[i];
|
|
data[i] = data[j];
|
|
data[j] = swap;
|
|
}
|
|
|
|
// EXIT;
|
|
}
|
|
|
|
~heap()
|
|
{
|
|
if constexpr (std::is_trivially_copyable_v<T>)
|
|
{
|
|
free(data);
|
|
}
|
|
else
|
|
{
|
|
delete[] data;
|
|
}
|
|
}
|
|
};
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|