Loading...
Please wait, while we are loading the content...
Similar Documents
Inorder Traversal of a Binary Heap and its Inversion in Optimal Time and Space (1992)
| Content Provider | CiteSeerX |
|---|---|
| Author | Schoenmakers, Berry |
| Abstract | In this paper we derive a linear-time, constant-space algorithm to construct a binary heap whose inorder traversal equals a given sequence. We do so in two steps. First, we invert a program that computes the inorder traversal of a binary heap, using the proof rules for program inversion by W. Chen and J.T. Udding. This results in a linear-time solution in terms of binary trees. Subsequently, we data-refine this program to a constant-space solution in terms of linked structures. 1 |
| File Format | |
| Publisher Date | 1992-01-01 |
| Publisher Institution | Mathematics of Program Construction, volume 669 of Lecture Notes in Computer Science |
| Access Restriction | Open |
| Subject Keyword | Optimal Time Inorder Traversal Proof Rule Constant-space Solution J.t. Udding Linear-time Solution Binary Tree Program Inversion Binary Heap Constant-space Algorithm |
| Content Type | Text |
| Resource Type | Article |
