Re: Optimizing basic operations
- Posted by DerekParnell (admin) Aug 21, 2013
- 4400 views
Derek,
Looking at your code I notice that your implementation of
insert_record is faulty. If you insert data on increasing
key values into a max-heap the code appears to generate a
linked list.
You say that the tree is not balanced: but a heap is
required to be a coplete tree - no gaps except the bottom
row which is filled from left to right.
Thank you for looking into this code. I appreciate peer reviews.
The insert_record() function is not faulty in the respect you mention. Now as you say, inserting records in priority order will create a linked list. However, note that a linked list is a variant of a tree, one in which each node has at most one child. Also, a priority queue (heap structure) is not bound to be implemented as a binary tree, although it can be, and arguably should be as that could give better insertion speed. The Heap can actually be implemented in any of a number of ways, each has it's own strengths and weakness. My implementation assumed that records would be added in a random manner.
But in any case, I'll have a go tonight at adding a 'balancing' algorithm to help flatten out the tree, regardless of the insertion order. But remember main the purpose of a Heap is to quickly retrieve the highest priority record - though your requirements might differ.
