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.

About these ads

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_.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 621 other followers

%d bloggers like this: