Browse Prior Art Database

Two Algorithms for Maintaining Order in a List

IP.com Disclosure Number: IPCOM000148173D
Original Publication Date: 1988-Sep-15
Included in the Prior Art Database: 2007-Mar-29
Document File: 22 page(s) / 1M

Publishing Venue

Software Patent Institute

Related People

Sleator, Daniel D.: AUTHOR [+3]

Abstract

Paul F. Dietz Department of Computer Science University of Rochester Rochester, NY 14627 Daniel D. Sleator Computer Science Department Carnegie Mellon Unjversity Pittsburgh, PA 15213 Abstract The order maintenance problem is that of maintaining a list under a se- quence of Insert and Delete operations, while answering Order queries (deter- mine which of two records comes first in the list). We give two new algorithms for this problem. The first algorithm matches the O(1) amortized time per operation of the best previously known algorithm, and is much simpler. The second algorithm permits all operations to be performed in O(1) worst-case time. 'A preliminary version of this paper was presented at the 19th Annual ACM Symposium on Theory of Computing, New York, May 25-27, 1987. 2This author was employed by Schlumberger-Doll Research, Ridgefield, Connecticut, at the time this work was done. 3Partial support provided by DARPA, ARPA order 4976, amendment 20, monitored by the Air Force Avionics Laboratory under contract F33615-87-C-1499, and by the National Science Foundation under grant CCR-8658139.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 9% of the total text.

Page 1 of 22

Two *Algorithms for Maintaining Order in a List

Daniel D. Sleator ' and Paul F. Dietz
1.5 September 1988

  'Partial support provided by DAXPA, ARPA. order 4976, amendment 20, monitored by the Air Force Avionics Laboratory under contract F33615-87-C-1499,
and by the National

Science Foundation under grant CCR-8658139.

                               The views and conclusions contained in this document are thoae of the authors and should not be interpreted as representing the official policies, either exprersed or implied, of the Air Force Avionics Laboratory, the National Science Foundation or the US Government.

[This page contains 1 picture or other non-text object]

Page 2 of 22

[This page contains 1 picture or other non-text object]

Page 3 of 22

Two Algorithms for Maintaining Order in a List

Paul F. Dietz

Department of Computer Science

University of Rochester Rochester, NY 14627

Daniel D. Sleator

Computer Science Department

Carnegie Mellon Unjversity
Pittsburgh, PA 15213

Abstract

  The order maintenance problem is that of maintaining a list under a se- quence of Insert and Delete operations, while answering Order queries (deter- mine which of two records comes first in the list). We give two new algorithms for this problem. The first algorithm matches the O(1) amortized time per operation of the best previously known algorithm, and is much simpler. The second algorithm permits all operations to be performed in O(1) worst-case time.

  'A preliminary version of this paper was presented at the 19th Annual ACM Symposium on Theory of Computing, New York, May 25-27, 1987.

  2This author was employed by Schlumberger-Doll Research, Ridgefield, Connecticut, at the time this work was done.

  3Partial support provided by DARPA, ARPA order 4976, amendment 20, monitored by the Air Force Avionics Laboratory under contract F33615-87-C-1499, and by the National Science Foundation under grant CCR-8658139.

v

[This page contains 1 picture or other non-text object]

Page 4 of 22

1. Introduction

A variety of important problems in the design of data structures arise from the need to store and manipulate ordered sets of records. These problems can be formulated as a collection of operation types, each with an anticipated frequency of occurrence. A data structure is desired which performs efficiently on the operations which occur with high frequency.

The most versatile data structure for solving these problems is the binary search tree
[13]. In some circumstances the commonly used operations do not require the full generality of binary search trees, and faster methods are possible. In this paper, we consider one of these special problems.

  The order maintenance problem is that of maintaining a non-empty list L of records under a sequence of the following three types of operations:

Insert(x, y): Insert record y after record x in the list. The record y must not already be in the...