Theory of Trinomial Heaps

Type of content
Theses / Dissertations
Publisher's DOI/URI
Thesis discipline
Degree name
Other
Publisher
University of Canterbury
Journal Title
Journal ISSN
Volume Title
Language
English
Date
2002
Authors
Takaoka, Tadao
Abstract

We design a new data structure, called a trinomial heap, which supports the decrease-key in O(1) time, and an insert operation and delete-min operation in O(log n) time, both in the worst case, where n is the size of the heap. The merit of the trinomial heap is that it is conceptually simpler and easier to implement than the previously invented relaxed heap. The relaxed heap is based on binary linking, while the trinomial heap is based on ternary linking.

Description
Citation
Keywords
Ngā upoko tukutuku/Māori subject headings
ANZSRC fields of research
Rights
All Right Reserved