Theory of 3-4 Heap
| dc.contributor.author | Bethlehem, Tobias | en |
| dc.date.accessioned | 2008-12-10T22:18:22Z | |
| dc.date.available | 2008-12-10T22:18:22Z | |
| dc.date.issued | 2008 | en |
| dc.description.abstract | 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'. | en |
| dc.identifier.uri | http://hdl.handle.net/10092/1930 | |
| dc.identifier.uri | http://dx.doi.org/10.26021/1447 | |
| dc.language.iso | en | |
| dc.publisher | University of Canterbury. Computer Science and Software Engineering | en |
| dc.relation.isreferencedby | NZCU | en |
| dc.rights | Copyright Tobias Bethlehem | en |
| dc.rights.uri | https://canterbury.libguides.com/rights/theses | en |
| dc.subject | 3-4 heap | en |
| dc.subject | 2-3 heap | en |
| dc.subject | Fibonacci | en |
| dc.subject | Dijkstra | en |
| dc.title | Theory of 3-4 Heap | en |
| dc.type | Theses / Dissertations | |
| thesis.degree.discipline | Computer Science | en |
| thesis.degree.grantor | University of Canterbury | en |
| thesis.degree.level | Masters | en |
| thesis.degree.name | Master of Science | en |
| uc.bibnumber | 1116402 | en |
| uc.college | Faculty of Engineering | en |
Files
Original bundle
1 - 1 of 1