- Your names.
pvt
is pretty poor and P
is, frankly, quite dismal as names go. I'm still not sure what P
is really supposed to mean.
- you've used a fixed-size array where it's not really suitable. If your heap contains fewer than 10000 items, it wastes space. If a user tries to add more than 10000 items, they overflow the space you've allocated, leading to undefined behavior. Much better to use (for example) a
std::vector
that will grow the allocation as needed to approximate the size actually in use.
Writing your own code to exchange items:
int temp=arr[x];
arr[x]=arr[x*2];
arr[x*2]=temp;
...is almost never as expressive as using std::swap
to do the job. I find std::swap(arr[x], arr[x*2]);
much more readable. If you want to support using a specialized swap
in case the user has provided one for the type being stored, you can use an idiom like:
using std::swap;
swap(arr[x], arr[x*2]);
This way if there's a swap
for the type of arr[x]
(defined in the same namespace as that type) it'll be found via Koenig lookup and used for the swap. If that doesn't exist, then std::swap
will be found because of the using
declaration.
Your current code is limited to storing int
s in the heap for no particularly good reason. About the only real requirement for a heap is that items satisfy a strict weak ordering (you must be able to compare them, and comparisons must be transitive so if a<b
and b<c
, then a<c
).
- along the same lines, you could allow the user to specify a function/object to use to compare items. This allows you to use the same code for either a min-heap or a max-heap by simply changing the comparison.
- Bonus: Ideally, I'd probably prefer to access the heap via iterators so I could use it with standard algorithms and such.
Based on those, I'd prefer to see the skeleton of the code look something like this:
template <class T, class cmp=std::less<T>>
class heap {
std::vector<T> data;
public:
heap();
template<class Iter>
heap(Iter b, Iter e); // construct a heap from the elements pointed to by two iterators
void insert(T);
T extract();
};
I should probably note that the T extract();
has a potential problem with exception safety. I've assumed (for the moment) that the type being stored never throws on copy/move. If it could throw on copy/move, then T extract()
wouldn't be exception safe. The problem is much the same as a pop
from a stack that returns the popped value: if the copy/move to return the item throws an exception, the user doesn't receive the item, but the item has already been removed from the heap, so the item is lost and can't be retrieved.
If T
might throw exceptions on copy/move, you typically want to change the interface to something more like:
T get_min(); // just retrieves smallest item, without removing it from the heap.
void pop(); // just removes smallest item
This lets the user retrieve the smallest item, then if and only if that succeeds, remove the smallest item from the heap. Oddly, they don't need to check for that succeeding though:
T x = myheap.get_min();
myheap.pop();
If the first statement throws an exception, then the second statement won't execute, and the heap remains unchanged. If the first doesn't throw, then the second executes with (presumably) no chance of throwing.
That last condition raises another point, however: in nearly every case, you need some assurance about at least a few operations not throwing. In this case, we depend on being able to swap items without ever throwing, or we can't remove an item from the heap dependably--if swapping might throw, then attempting to remove an item could corrupt the heap.
auto
keyword andnullptr
). \$\endgroup\$