PTrie: Priority Queue based on multilevel prefix tree
| dc.contributor.author | David, Planeta | en_US |
| dc.date.accessioned | 2007-04-04T20:21:51Z | |
| dc.date.available | 2007-04-04T20:21:51Z | |
| dc.date.issued | 2006-04-20 | en_US |
| dc.description.abstract | Tree structures are very often used data structures. Among ordered types of trees there are many variants whose basic operations such as insert, delete, search, delete-min are characterized by logarithmic time complexity. In the article I am going to present the structure whose time complexity for each of the above operations is O(M/K + K), where $M$ is the size of data type and $K$ is constant properly matching the size of data type. Properly matched $K$ will make the structure function as a very effective Priority Queue. The structure size linearly depends on the number and size of elements. PTrie is a clever combination of the idea of prefix tree -- Trie, structure of logarithmic time complexity for insert and delete operations, doubly linked list and queues. | en_US |
| dc.format.extent | 214890 bytes | |
| dc.format.mimetype | application/pdf | |
| dc.identifier.citation | http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cis/TR2006-2023 | en_US |
| dc.identifier.uri | https://hdl.handle.net/1813/5722 | |
| dc.language.iso | en_US | en_US |
| dc.publisher | Cornell University | en_US |
| dc.subject | computer science | en_US |
| dc.subject | technical report | en_US |
| dc.title | PTrie: Priority Queue based on multilevel prefix tree | en_US |
| dc.type | technical report | en_US |
Files
Original bundle
1 - 1 of 1