## 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 *i*th node at 2*i* and 2*i*+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

`DeleteMax`

doesn’t work. Harrumph! I’ll work on it this evening. Sorry.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.

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