Re: Optimizing basic operations
- Posted by gimlet Aug 21, 2013
- 4292 views
Derek,
The point of using a heap is that it give O log N insert and extract min/max. It
is the basis of heapsort.
There are faults in your method:
1 Your method allows a wildly unbalanced tree. This is not the description of a heap.
Whether your heap would balance out in the long run - maybe - probably not.
2 Inserting from the top does not build a correct priority queue as it will
produce last in first out for any given priority. I don't think we want
to model queue-jumping.
3 Testing with random key data will generate a balanced tree - as such it is not a fair
test.
4 When you do extract min/max you promote one of its children - this may further
unbalance your tree.
The (standard) array approach is clean and simple. Is there some pressing reason
that requires you use pointers? Your code is quite complex.
