1
$\begingroup$

I have a priority queue implementation which I claim has the following worst case asymptotic run-times for the given operations:

  • PEEK_MIN …………………………… O(1)
  • POP_MIN…………………………… O( (INVERSE_Γ(n)) ^2).
  • INSERT_XKEY…………………………… O( (INVERSE_Γ(n)) ^2).
  • DELETE_IKEY…………………………… O( (INVERSE_Γ(n)) ^2).

n denotes the number of elements in the priority queue. Γ denotes the gamma function, Γ is essentially the factorial function if the input argument is a positive integer.

The claim to the run-times above seems dubious. O( (INVERSE_Γ(n)) ^2) is an extremely slow growing function. This is a better run-time than logarithmic time. Runtimes for well-known priorities queues can be found on Wikipedia

We implement the priority queue as a heap. This special heap is a balanced tree. However, unlike balanced binary, ternary, quaternary trees, etc… nodes in this special tree do not all have the same maximum number of children.

The root node has 1 child; the child of the root has 2 children; each child of a child of the root has 3 children.

spreading heap

The numbers in the diagram above are not priority queue keys. They are the number of children each node has.

In general, for any natural number d, the nodes at depth d have (d+1) children. The depth of the root node is 0, not 1.

Suppose that h is the height (max depth) of the tree.

Then the tree has 1∗2∗3∗4∗…∗d leaves.

If n is the number of nodes in the tree, then d = O(INVERSE_Γ(n))

The number of nodes in the tree is even greater than the number of leaves. Specifically, the total number of nodes is the sum of k! from k = 1 to k = n. Therefore, the asymptotic upper bound given for the depth of the tree as a function of the number of nodes in the tree is not tight.

Each node does not have a pointer to each of its children. For example, if a node has 50 children, it does not have 50 pointers -- one for each child. Instead, the children of each node are in a linked list. Each node has one a pointer to the head of a linked list of children. Finding the child of a node having the largest key value will be done by linear search of the linked list.

class MinHeapNode<KeyType> {
    Variables:
        LinkedList<MinHeapNode> Kids;
        MinHeapNode<KeyType>  Parent;
}
class MinHeap<KeyType>  {
    Variables:
        MinHeapNode<KeyType>  root;
        MinHeapNode<KeyType>  write_head;
        MinHeapNode<KeyType>  left_leaf;
        int numel; // number of elements
}

This heap is a left-justified balanced heap. The write_head is the leftmost null leaf. The write_head is where any new node would be inserted.

By “balanced” we mean that there exists a positive integer h such that all non-null leaf nodes are either distance h or (h-1) away from the tree root.

SWAP_KEYS(MinHeapNode L, MinHeapNode R) {
        old_L_key = L.key
        sml.key = R.key
        R.key = old_L_key
}

SWAP_KEYS runs in O(1).

BUBBLE_UP_ONCE(MinHeapNode parent) {
    did_bubble = false
    // all child nodes supposed to have larger keys than parent
    sml = LINEAR_SEARCH_MIN(parent.kids); // linked list
    if (sml.key < parent.key) {
        SWAP_KEYS(sml, parent);
        did_bubble = true;
    }
    return did_bubble;
}

BUBBLE_UP_ONCE runs in O(child_count) where child_count is the number of children in a node’s linked list. BUBBLE_UP_ONCE runs in O(d) time where d is the distance of the node to the root.

BUBBLE_MANY(MinHeapNode knode) {
    did_bubble = true;
    while (did bubble) {
        did_bubble = BUBBLE_UP_ONCE(knode);
    }
}

At worst, BUBBLE_MANY bubbles a leaf all the way to the root of the heap. Let max_depth be the height/max depth of the tree We linear search the linked list of children of a node at max_depth
linear search the children of a node at max_depth – 1;
linear search the children of a node at at max_depth – 2; and so on…

The number of children of a node at depth d is approximately d. So BUBBLE_MANY runs in O(1 + 2 + 3 + … + h) = O(h^2). However, ∗h∗ is ∗∗∗NOT∗∗∗ the number of nodes in tree. n is the number of nodes in the tree. Thus, the runtime of BUBBLE_MANY is O( (INVERSE_Γ(n)) ^2).

INSERT_A_NODE(MinHeap H, KeyType new_key) {
    new_node = H.WRITE_NEW_NODE(new_key);
    BUBBLE_MANY(new_node);
    H.INCREMENT_NUMEL() // NUMBER OF ELEMENTS
    Return; 
}

DELETE_A_NODE(MinHeap H, MinHeapNode delete_me) {
    del_key = delete_me.key;
    wh = H.GET_WRITE_HEAD();
    delete_me.key = wh.key;
    H.DESTROY_WRITE_HEAD();
    BUBBLE_MANY(delete_me);
    H.DECREMENT_NUMEL() // NUMBER OF ELEMENTS
    Return del_key; 
}

POP_MIN takes the key from the rightmost leaf node (the write head) and puts it in the root node. The root key is then bubbled toward the leaves. At worst, have to swap keys of parent and child until get to leaf-level. One linear search of the children of each node to find the largest child. Cost is O(1 + 2 + 3 + 4 + … + depth)
depth = (INVERSE_Γ(n) of n)b
POP_MIN Pop root also O( (INVERSE_Γ(n)) ^2).

$\endgroup$
2
$\begingroup$

Stirling's formula states that $\Gamma(m) = \exp \Theta(m\log m)$. Suppose that $m = \Gamma^{-1}(n)$, i.e., $n = \Gamma(m)$. Taking logarithms, we get $\log n = \Theta(m\log m)$, and so $m = \Theta(\frac{\log n}{\log\log n})$. In other words, $$ \Gamma^{-1}(n) = \Theta \left( \frac{\log n}{\log \log n} \right). $$ Therefore your running times, which are quadratic in $\Gamma^{-1}(n)$, are in fact super-logarithmic.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.