# interval heap
# www.keithschwarz.com/interesting/code/?dir=interval-heap

# pq[1..n, "lo"|"hi"] is the priority queue
# size is the number of elements in the queue

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"] }

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

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 } }

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 } }