Double-Ended Priority Queues

September 27, 2013

As with imperative heaps, we will implement interval heaps in Awk, because the array manipulations become intolerable in Scheme. We keep two global variables: the priority queue itself is stored in the global variable pq, which is subscripted by the node number (indexed from 1) and either “lo” or “hi”, and the number of items currently present in the interval heap is stored in the global variable size. If size is odd, the last node will contain a single item, which can be considered as a member of both the min-heap of lo items and the max-heap of hi items but is always stored in the “lo” field; that fact causes considerable ugliness in the code, as we shall see. The first three functions are trivial, but note that getMax is more complicated than getMin precisely because of the ambiguity of the last node:

function isEmpty() { return (size == 0) }

function getMin() {
    if (size == 0) return "error: out of bounds"
    return pq[1, "lo"] }

function getMax() {
    if (size == 0) return "error: out of bounds"
    if (size == 1) return pq[1, "lo"]
    return pq[1, "hi"] }

The insert function adds the new item to the last node, then either sifts up the min-heap, or sifts up the max-heap, or leaves things alone, depending on the priority of the new item. Note the complications that arise from the irregular last node:

function insert(item, parent, child, last, temp) {
    last = int((size + 1) / 2)

    # add new item to proper position in last node
    if (size % 2 == 0) {
        last = last + 1
        pq[last, "lo"] = item }
    else if (item < pq[last, "lo"]) {
        pq[last, "hi"] = pq[last, "lo"]
        pq[last, "lo"] = item }
    else pq[last, "hi"] = item

    size = size + 1; if (size <= 2) return
    child = last; parent = int(child / 2)

    if (item < pq[parent, "lo"]) {

        # sift up minHeap
        while (child > 1) {
            if (pq[parent, "lo"] <= pq[child, "lo"])
                break
            temp = pq[parent, "lo"]
            pq[parent, "lo"] = pq[child, "lo"]
            pq[child, "lo"] = temp
            child = parent; parent = int(child / 2) } }

    else if (pq[parent, "hi"] < item) {

        # sift up maxHeap, handle singleton
        while (child > 1) {
            if ((child SUBSEP "hi") in pq) {
                if (pq[child, "hi"] <= pq[parent, "hi"])
                    break
                temp = pq[parent, "hi"]
                pq[parent, "hi"] = pq[child, "hi"]
                pq[child, "hi"] = temp }
            else {
                if (pq[child, "lo"] <= pq[parent, "hi"])
                    break
                temp = pq[parent, "hi"]
                pq[parent, "hi"] = pq[child, "lo"]
                pq[child, "lo"] = temp }
            child = parent; parent = int(child / 2) } }

    else {} } # in proper position, nothing to do

The problem of the irregular last node affects the code in two places, when adding the new item to the last node and when sifting up the max-heap; note that sifting up the min-heap is not affected.

Deleting the minimum is done by replacing the lo item in the root with the minimum item in the last element, then sifting it down to its proper place; at each step the item is swapped with its smaller child until it is larger than the smaller child, which stops the process:

function deleteMin( last, parent, child, sibling, temp) {
    if (size == 0) return "error: out of bounds"
    if (size == 1) { size = 0; delete pq[1, "lo"]; return }
    if (size == 2) { size = 1; pq[1, "lo"] = pq[1, "hi"]
                     delete pq[1, "hi"]; return }
    last = int((size + 1) / 2)

    # move min element of last node to root
    pq[1, "lo"] = pq[last, "lo"]
    if (size % 2 == 1) {
        delete pq[last, "lo"]
        last = last - 1 }
    else {
        pq[last, "lo"] = pq[last, "hi"]
        delete pq[last, "hi"] }
    size = size - 1

    # sift down min element
    parent = 1; child = 2; sibling = 3
    while (child <= last) {
        if (sibling <= last && pq[sibling, "lo"] < pq[child, "lo"])
            child = sibling
        if (pq[parent, "lo"] <= pq[child, "lo"])
            break
        temp = pq[parent, "lo"]
        pq[parent, "lo"] = pq[child, "lo"]
        pq[child, "lo"] = temp
        if (size % 2 == 0 && pq[child, "hi"] < pq[child, "lo"]) {
            temp = pq[child, "hi"]
            pq[child, "hi"] = pq[child, "lo"]
            pq[child, "lo"] = temp }
        parent = child; child = parent * 2; sibling = child + 1 } }

DeleteMax is similar to deleteMin, but with the sense of the comparisons reversed, except that it suffers even more from the problem of the irregular last element:

function deleteMax( last, parent, child, sibling, temp) {
    if (size == 0) return "error: out of bounds"
    if (size == 1) { size = 0; delete pq[1, "lo"]; return }
    if (size == 2) { size = 1; delete pq[1, "hi"]; return }
    last = int((size + 1) / 2)

    # move max element of last node to root
    if (size % 2 == 0) {
        pq[1, "hi"] = pq[last, "hi"]
        delete pq[last, "hi"] }
    else {
        pq[1, "hi"] = pq[last, "lo"]
        delete pq[last, "lo"]
        last = last - 1}
    size = size - 1

    # sift down max element
    parent = 1; child = 2; sibling = 3
    while (child <= last) {
        if (sibling == last && size % 2 == 0 &&
            pq[child, "hi"] < pq[sibling, "hi"])
                child = sibling
        else if (sibling == last && size % 2 == 1 &&
                 pq[child, "hi"] < pq[sibling, "lo"])
                child = sibling
        else if (pq[child, "hi"] < pq[sibling, "hi"])
                child = sibling
        if (size % 2 == 0 && pq[child, "hi"] < pq[parent, "hi"])
            break
        else if (size % 2 == 1 && pq[child, "lo"] < pq[parent, "hi"])
            break
        temp = pq[parent, "hi"]
        pq[parent, "hi"] = pq[child, (size % 2 == 0) ? "hi" : "lo"]
        pq[child, (size % 2 == 0) ? "hi" : "lo"] = temp
        if (size % 2 == 0 && pq[child, "hi"] < pq[child, "lo"]) {
            temp = pq[child, "hi"]
            pq[child, "hi"] = pq[child, "lo"]
            pq[child, "lo"] = temp }
        parent = child; child = parent * 2; sibling = child + 1 } }

You can see the complete code at http://programmingpraxis.codepad.org/arnlgy5B.

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 628 other followers

%d bloggers like this: