The Heap Structure and Its Applications
Main Article Content
Abstract
A heap is a partially sorted binary tree. Like the binary trees, heaps have a meaning for the Left and Right subtrees. The root of a heap is guaranteed to hold the largest node in the trees; its subtrees contain data that have lesser values. Unlike the binary search tree, however, the smaller nodes of a heap can be placed on either the Right or Left subtree. Therefore, both the Left and Right branches of the tree have the same meaning .Heaps have another interesting facet: They are often implemented in an array rather than a linked list. This implementation is possible because the heap is, by definition, complete or nearly complete. This allows a fixed relationship between each node and its children. There are two factors at work: the time it takes to create a heap by adding each element and the time it takes to remove all of the elements from a heap. Fortunately, we have a guarantee that adding a single element to and removing a single element from a heap both take O(log(n)) time.
Keywords: Heap, Reheapup, Reheapdown, Maxheap, Minheap
Downloads
Article Details
COPYRIGHT
Submission of a manuscript implies: that the work described has not been published before, that it is not under consideration for publication elsewhere; that if and when the manuscript is accepted for publication, the authors agree to automatic transfer of the copyright to the publisher.
Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work
- The journal allows the author(s) to retain publishing rights without restrictions.
- The journal allows the author(s) to hold the copyright without restrictions.