Using Pascal's Triangle to implement queues and stacks using heaps

Question

I have the following question as homework in an algorithms, analysis and data structures class:

And here's an answer I wrote up:

A queue is a first-in-first-out data structure. A heap is a data structure that makes searching for objects in a sortable space faster than linear search.

Now, every data structure needs to implement at least four basic operations: create, read, update, and delete. In this case, create would add an object to the queue-heap, read would return information about an object in the queue-heap, update would change somevalue in an object in the queue-heap, and delete would remove an object from the queue-heap.

Because the public interface of this data structure is presented as a queue, there are several design considerations to make: should it be possible to read objects only from the front of the queue? What about the middle of the queue? The back? And so on for creating ( or inserting ) objects in the queue, updating, removing and so on. Similarly, the public interface ought to implement methods such as "get next" or "pop front", "get previous" or "pop back", "cycle to next", "cycle previous", and so on.

In fact, one might argue that the only invariant property of a queue is that it records some sense of order amongst objects: regardless of how the queue got in any given state, at any given moment some object is first, some other object is second, another object is third, and so on.

So, we have to record order.

Suppose you put objects in the heap not based on their value, but rather gave each object a natural number corresponding to its order in the queue. Then, the root element of the heap would be position one in the queue, the root's left child would be the second item in the queue, the root's right child would be the third element in the queue and so on.

Now, when we try to implement queue-like methods such as "get next", "get previous", etc. we have a problem: given any object in the heap, if we are asked to get the object to the left or the right in the queue, we have to somehow interpolate from the object's place in line ( a natural number ) how to traverse the parent, children, siblings, and cousins in order to return the correct object.

Notice, however, that there is a neat bijection from each object's place in the queue ( a natural number ) to the n-choose-k address of a slot in Pascal's Triangle: the first object in the queue is zero-choose-zero, the second object is one-choose-zero, third is one-choose-one, the fourth is three-choose-zero, the fifth object is three-choose-one, the seventh is three-choose-three, the eighth is seven-choose-zero, and so on.

Here are the first few elements of the bijection again written as a sequence: < (0,0), (1,0), (1,1), (3,0), (3,1), (3,2), (3,3), (7,0), ..., (7,7), (15,0), ... >

In other words, the place of an object in the queue is determined by the bijection f(n,k) = n + k + 1.

So, rather than recording the place of an object in the queue via natural number, record it on the object using the tuple, n-choose-k address of a position in Pascal's Triangle.

Similarly, store metadata about the queue-heap on the main data structure itself. Namely, the tuple, n-choose-k address of the last element in the queue, a pointer to the object that is currently considered the front of the queue, etc. ( You could also cycle objects so that the object at the front of the queue is always at the root of the heap, but that might be less efficient than simply abusing space consumption, procedurally cycling through the queue using arithmetic on n-choose-k tuples, and running garbage collection based on some sort of load factor. )

Some of the queue-like methods could be implemented like this:

procedure queueHeap.getNext():
    if this.current.n == this.current.k:
        next = this.read(2^(this.current.n + 1) - 1,0);
    else
        if isEven(this.current.k):
            next = this.current.parent.rightChild;
        else:
            next = this.current.parent.parent.rightChild.leftChild;

    return next;

procedure queueHeap.read(n,k) can use modular arithmetic and relationships between the n-choose-k addresses of the object under a "read head" and the object being sought to navigate from the root of the heap to the object being sought directly.

So, it is possible to implement a queue as a heap using n-choose-k tuples as addresses as well as a stack. ( A stack would merely present different methods on the data structure's public interface to give the end user a sense of first-in-first-out ordering. )

Is this implementation correct? Is it novel? Is it efficient?

Answer 1

I assume that the data stuctures given are abstract. They can only be updated using their interface operations.

A (fifo) queue has indeed init, enqueue(item) "at the end", dequeue(item) retrieve "from the beginning" and the test isempty. Upto small personal preferences.

I also think that the heap here means the binary heap implementation of the priority queue, which keeps a set of items with their piorities, and has similarly init, add(item,prio) any item , delmax(item) remove the item with maximal priority and the test isempty. Perhaps also getmax(item) to look at the maximal element without deleting.

That's all. No explicit positions you can look at or refer to. Positions are used in implementing the data structures usually using an array (for binary heap, or fixed size queue) or a pointer list.

For me the only feasible way to implement a queue using a heap is to use the priorities to get the elements in the same order as the linear order of the queue. Start with priority zero for the first element added, and decrease the priority for each next element, so that the first element always has highest priority and is retrieved using getmax to implement dequeue.

As you are given a heap, perhaps you are also allowed to use the standard operations that move the elements up and down the heap, as part of the implementation. However these operations are also priority based and do not explicitly look at positions, so I do not see much advantage here.