As an alternative to the Fibonacci heap, and a variation of the 2-3 heap data structure by Tadao Takaoka, this research presents the 3-4 heap data structure. The aim is to prove that the 3-4 heap, like its counter-part 2-3 heap, also supports n insert, n delete-min, and m decrease-key operations, in O(m + nlog n) time. Many performance tests were carried out during this research comparing the 3-4 heap against the 2-3 heap and for a narrow set of circumstances the 3-4 heap outperformed the 2-3 heap.
The 2-3 heap has got a structure based on dimensions which are rigid using ternary linking and this path is made up of three nodes linked together to form a trunk, and the trunk is permitted to shrink by one. If further shrinkage is required then an adjustment is made by moving a few nodes from nearby positions to ensure the heaps rigid dimensions are retained. Should this no longer be the case, then the adjustment will trigger a make-up event, which propagates to higher dimensions, and requires amortised analysis. To aid amortised analysis, the trunk is given a measurement value called potential and this is the number of comparisons required to place each node into its correct position in ascending order using linear search.
The divergence of the 3-4 heap from the 2-3 heap is that the trunk maximum is increased by one to four and is still permitted to shrink by one. This modified data structure will have a wide range of applications as the data storage mechanism used by graph algorithms such as Dijkstra's 'Single Source Shortest Path'.
| Identifer | oai:union.ndltd.org:canterbury.ac.nz/oai:ir.canterbury.ac.nz:10092/1930 |
| Date | January 2008 |
| Creators | Bethlehem, Tobias |
| Publisher | University of Canterbury. Computer Science and Software Engineering |
| Source Sets | University of Canterbury |
| Language | English |
| Detected Language | English |
| Type | Electronic thesis or dissertation, Text |
| Rights | Copyright Tobias Bethlehem, http://library.canterbury.ac.nz/thesis/etheses_copyright.shtml |
| Relation | NZCU |
Page generated in 0.0027 seconds