It's not a heap, it's just an ordered map. Specifically, the ScriptList class is a std::map
, and also maintaining a reverse mapping from values to keys in another std::map.
Typically std::map is implemented via a balanced search tree (most often a red-black tree
) which is not the same as a heap
Theoretically, a red-black tree has worse asymptotic performance than a heap, when all you want is to pull items out of a collected in sorted order. But, if you have a heap implemented in a poorly optimised interpreted language like Squirrel and compare it to a red-black tree implemented in C++ native code, the red-black tree ends up having better constant factors.
Finding the smallest element in a search tree is traversing down the left branch to the leftmost leaf node. In a balanced tree this visits log(n) nodes, so this is an O(log(n)) operation. (In a heap this is a constant time operation.)
Inserting an item in a red-black tree is O(log(n)), and can involve a lot or re-balancing. (On average a binary heap is constant time, but worst-case is also O(log(n)).)
Removing an item in a red-black tree is O(log(n)). (Same as a heap.)
Getting count of items is a constant time operation. (Same as a heap.)
Checking for existence of an item in a balanced search tree is O(log(n)). (Better than a heap, which is O(n).)
If you were comparing a priority queue implemented as a heap in C++ with one implemented as a red-black tree in C++, the heap would win, for several of these reasons. One of the big reasons would likely be cache locality, since a heap uses an array with contiguous memory, while a tree uses individual allocations for each item.
But the name "NativeHeap" is wrong. It's not a heap.