Deques with heap order

Hania Gajewska, Robert E. Tarjan

Research output: Contribution to journalArticlepeer-review

32 Scopus citations


A deque with heap order is a deque (double-ended queue) such that each item has a real-valued key and the operation of finding an item of minimum key is allowed as well as the usual deque operations. By combining a standard deque implementation with an auxiliary heap (priority queue) it is possible to implement a deque with heap order so that the worst-case time per operation is O(log n), where n is the number of items on the deque. This paper describes an implementation of deques with heap order for which the worst-case time per operation is O(1).

Original languageEnglish (US)
Pages (from-to)197-200
Number of pages4
JournalInformation Processing Letters
Issue number4
StatePublished - Apr 17 1986
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Information Systems
  • Signal Processing
  • Computer Science Applications


  • Deques
  • data structures
  • heaps
  • priority queues


Dive into the research topics of 'Deques with heap order'. Together they form a unique fingerprint.

Cite this