Implementation in C++ of an efficient heap structure, with an additional index. We are interested in having a vector where computing the minimal value is fast : hence, the purpose of the index is to retain the permutation made when heapif-ied, and at every operation / swap on the table, to maintain this index, such that the structure apparently acts like a vector.
The following operations will be implemented :
heapify: creates the heap from a table (note : make faster when the structure is already 'well-sorted' / when copying ... ?)read-min: reads the minimal value (in constant time)incr/decr: modifies the value for some index, and maintains the heap structure. For making operations faster and answering only some specific needs, we do not implement a general modification- some
copyorextendoperation may be useful (when padding with zeros, for our needs again)
The heaps will get a fixed size : therefore, insertion / deletion won't be implemented.