Diamond deque: A simple data structure for priority deques (Q685528)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Diamond deque: A simple data structure for priority deques |
scientific article |
Statements
Diamond deque: A simple data structure for priority deques (English)
0 references
13 January 1994
0 references
A simple pointer-free data structure is proposed to implement priority deques. The two heaps (a min-heap and a max-heap) of a twin-heap are stored in one linear array. The simple parent-child relationship of a traditional heap is retained. The min-heap and the max-heap will jointly grow and shrink at one end of the linear array. The proposed data structure is named a diamond deque because of the diamond shape of its Hasse diagram. Priority deque operations on a diamond deque are as efficient as on a twin-heap, a min-max heap, or a deap. Because a diamong deque is highly symmetrical, its interface relations between min-heap and max-heap are simpler. This makes it easier to implement in practice.
0 references
priority deques
0 references
heaps
0 references