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