Programming Praxis

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)

    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)

    # 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)

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

Pages: 1 2