## Double-Ended Priority Queues

### September 27, 2013

We have seen priority queues on several different occasions in the past, including this implementation using imperative heaps; such priority queues allow items to be inserted in any order and retrieved in order of priority. In today’s exercise we will look at a similar data structure called an interval heap that permits access at both ends, to either the minimum or maximum item in the heap. The permitted operations are:

isEmpty — is the priority queue empty?
insert item — insert a new item in the priority queue
getMin — get the smallest item in the priority queue
getMax — get the largest item in the priority queue
deleteMin — delete the smallest item from the priority queue
deleteMax — delete the margest item from the priority queue

Operation of an interval heap is similar to operation of an imperative heap, with a tree embedded in an array and the children if the ith node at 2i and 2i+1, except that each array element stores two items instead of one; all children of the array element are greater than or equal to the “lo” item of the array element and less than or equal to the “hi” item of the array element, at every node of the tree. The lo items from each element form a min-heap, in which each item is less than its children, and the hi items from each element form a max-heap, in which each item is greater than its children. New items are inserted at the end of the tree; if the new item is less then the lo item in the last element, it is sifted up to its proper position in the min-heap of lo items, if the new item is greater than the hi item in the last element, it is sifted up to its proper position in the max-heap of hi items, otherwise the new item is in its proper position. The minimum or maximum item in the interval heap can be deleted by removing it, replacing it with the corresponding minimum or maximum item from the last array element of the heap, then sifting down through the corresponding min-heap or max-heap.

Your task is to write functions that implement a double-ended priority queue using an interval heap as described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

### 3 Responses to “Double-Ended Priority Queues”

1. programmingpraxis said

`DeleteMax` doesn’t work. Harrumph! I’ll work on it this evening. Sorry.

2. Paul said

A version of a double ended priority queue in Python. In Python it is more efficient to use 2 heaps (a min and max heap) and keep cross-references between the corresponding items. If the top item is removed from one of the heaps the corresponding item in the other heap gets the tag “”. It is not necessary to rearrange the other heap.

```from heapq import heapify, heappop, heappush
from itertools import count
REMOVED = "<removed>"

def strip_id(queue):
"""strips the id from the queue"""
return [v for v, i in queue if i != REMOVED]

class DEQ(object):
def __init__(self, data=None):
self.entry_finder = {}
self.counter = count()
self.minq, self.maxq = [], []
if data:
for d in data:
self.insert(d)

def is_empty(self):
return not self.entry_finder

def insert(self, d):
id_ = next(self.counter)
mine, maxe = [d, id_],  [-d, id_]
heappush(self.minq, mine)
heappush(self.maxq, maxe)
self.entry_finder[self.id] = mine, maxe

def get_min(self):
self._check_empty(self.minq)
return self.minq[0][0]

def get_max(self):
self._check_empty(self.maxq)
return -self.maxq[0][0]

def pop_min(self):
self._check_empty(self.minq)
result,id_ = heappop(self.minq)
entries = self.entry_finder.pop(id_)
entries[1][1] = REMOVED
return result

def pop_max(self):
self._check_empty(self.maxq)
result,id_ = heappop(self.maxq)
entries = self.entry_finder.pop(id_)
entries[0][1] = REMOVED
return -result

def __str__(self):
return ("MIN" + str(strip_id(self.minq)) + "\nMAX" +
str([-x for x in strip_id(self.maxq)]))

def _check_empty(self, queue):
while queue and queue[0][1] == REMOVED:
heappop(queue)
if not queue:
raise ValueError("no data")
```
3. Paul said

In last line in the insert method self.id should replaced by id_.