• A Definition:
  • A "normal" d-heap is a tree with the property that a parent's "value" is not smaller than the "value" of any of its \(d\) children
  • An "inverted" heap is ordered the other way.
• Applications:
  • Priority Queue (i.e., a queue in which the elements are ordered based on their "priority" not their "arrival time"
  • Sorting

A 3-Heap

• Sift Down - move an element that is not properly positioned down the tree (i.e., towards its descendants)
• Sift Up - move an element that is not properly positioned up the tree (i.e., towards the root)

    siftup(i)
    {
        while (i is not the root node and i.value > i.parent.value) {

            swap(i, i.parent);
        }
    }
    

Suppose a node with value 44 is added to the end of the 3-heap above...

    siftdown(i)
    {
        while (i is not a leaf node and i.value < i.maxchild.value) {

            swap(i, i.maxchild);
        }
    }
    

Suppose the value of the root node is changed to 43...

    add(i)
    {
        add i to the back of the heap;

        siftup(i);
    }
    

    remove()
    {
        swap(front, back);

        remove the back element;

        siftdown(front);
    }
    

• Sift Down and Sift Up:
  • \(O(\log n)\)
• Add:
  • \(O(1)\) to add to the back
  • \(O(\log n)\) to sift up
• Remove:
  • \(O(1)\) to swap
  • \(O(1)\) to remove from the back
  • \(O(\log n)\) to sift down