DStruct02Demo

Demo notebook of the DStruct02 package

Version 2.0 — April 2005

Adriano Pascoletti

This notebook illustrates the usage of the package DStruct02.m, which defines a rather complete set of functions for the utilization of some ubiquitous data structures: stacks, FIFO queues, priority queues, balanced binary search trees. 
In particular, priority queues are implemented by means of both leftist heaps and binomial heaps (new in version 2.0), and binary search trees by means of both splay trees and  2-3 trees.
This version of the package provides full access to the internals of the data structures, but, on the other hand, it introduces some slight incompatibilities with previous versions (see MathSource entry Data structures).

This version of the package was developed and tested with Mathematica 5.1.

Preliminaries

Load the package assuming that the file DStruct02.m resides in a directory listed in $Path:

<< DStruct02`

Stacks

This implementation follows  D. Lichtblau: Data structures and efficient algorithms in Mathematica.

Symbols related to stacks are prefixed by sk:

?DStruct02`sk*

s=skNew[] generates a new empty stack s.

skPush[s, i] pushes item i onto stack s (s must be a symbol).

skPop[s] pops and returns an item from a stack s (s must be a symbol).

The first argument of skPush and skPop must be a symbol.

skTop[s] returns the item on top of a nonempty stack s.

skMakeEmpty[s] empties stack s  (s must be a symbol).

skEmptyQ[s] returns True iff stack s is empty.

skContents[s] lists the items in stack s (bottom to top).

This creates a new empty stack S, pushes some items, and shows the contents

S = skNew[];
Scan[
        skPush[S, #] &, {10, 5, 4, 8, 2, 20}];
skContents[S]

The stack is nonempty and its top element is 20

skEmptyQ[S]
skTop[S]

This pops an item and shows  the updated contents

skPop[S]
skContents[S]

Remove every stack item

skMakeEmpty[S]
skContents[S]

FIFO Queues

This implementation of FIFO queues follows  D. Lichtblau: Data structures and efficient algorithms in Mathematica.

Symbols related to FIFO queues are prefixed by q.

?DStruct02`q*

q=qNew[] creates a new empty queue named q.

qEnqueue[q, k] adds to queue q  a new item with key k (q must be a symbol).

qDequeue[q] removes an item from queue q and returns its key (q must be a symbol).

qMakeEmpty[q] empties queue q.

The first argument of qDequeue, qEnqueue, qMakeEmpty must be a symbol.

qKey[q, i] yields the key of item i of queue q.

qEmptyQ[q] returns True iff q is an empty queue (q must be a symbol).

qContents[q] returns the list of keys associated to the items of a  queue q (first to last).

qLength[q] returns the length of a  queue q.

qFirst[q] and qLast[q] yield the first and the last item of queue q, respectively.

Insert three elements into a new queue q and show its contents

q = qNew[];
Scan[
      qEnqueue[q, #] &, {"what", "you", "want", "inserted"}]; 
    qContents[q]

This yields the keys of the first and of the last item:

{qKey[q, qFirst[q]], qKey[q, qLast[q]]}

Dequeue and reenqueue an element:

qContents[q]
x = qDequeue[q]; qContents[q]
qEnqueue[q, x]; qContents[q]

Priority Queues I - Binomial Heaps

Priority queues are collections of items, each with an associated key. This implementation of (mergeable) priority queues uses binomial heaps.

Further details on binomial heaps can be found in 
T.H. Cormen, C.E. Leiserson, R.L. Rivest, Introduction to Algorithms, MIT Press, 2001.

A binomial heap is a forest of binomial trees and it is represented by a pair {rlist, order}. rlist denotes the list of roots of the forest trees, and  order an ordering criterion (the heap order).

Symbols related to binomials heaps are prefixed by bh:

?DStruct02`bh*

Basic operations:

bhNew[ord] builds a new empty binomial heap with ordering ord defaulting to Order[#1,#2]≥0&.

bhInsert[h, k] inserts an item with a given key k into a heap  h.

bhDelete[h, i] deletes item i from heap h.

bhDeleteMin[h] yields an item with minimal key, and deletes it from heap h.

The first argument of bhInsert, bhDelete, bhDeleteMin must be a symbol.

bhMin[h] returns an item of heap h with minimal key.

bhEmptyQ[h] returns True iff heap h is empty.

bhUnion[(Subscript[h, 1]), (Subscript[h, 2])]melds two heaps with the same ordering function; the resulting heap replaces (Subscript[h, 1]), and (Subscript[h, 2]) is emptied.
Both (Subscript[h, 1])and (Subscript[h, 2]) must be symbols.

bhContents[h, opts] yields a list of the contents of the forest trees using a sequence of options opts. Each tree is visited by an in-order traversal and its contents are displayed as

bhNode[item, key, <list of pointers to children>,parent, <contents of child 1>,
<contents of child 2>,…]

Possible options are: bhShowItems-> True|False, bhShowKeys-> True|False, bhShowParents-> True|False, lhShowPointers -> True|False with the obvious meaning.

Build a heap with four items and look at its contents:

b1 = 
      bhNew[]; bhInsert[
          b1, #] & /@ {"Make", "a", "new", "empty", "heap\
"}
bhContents[b1]

The forest consists of three trees: the first has a single item (item 5 with key heap), the second tree is empty, the third one has four items. 2 with key a is the root and it has two children: 1 has key Make and no children; 4 has key empty and a child: 3 with key new.

Other functions

bhKey[i] returns the key of item i.

bhChildren[i] and bhParent[i] return the list of children and the parent of item i.

bhOrder[h] returns the ordering function of a binomial heap h.

bhOrderedQ[h][expr] returns True if the parts of expression expr are ordered w.r. to  the ordering criterion of heap h.

bhOrdering[h][expr] returns the positions in expr at which each successive element of  Sort[expr,bhOrder[h]] appears.

Some data related to item 4:

{#, bhKey[#], bhChildren[#], bhParent[#]} &[4]

The typical sequence While queue ≠ empty do k← min key of queue; deletemin(queue);… end while can be coded as follows

While[¬ bhEmptyQ[b1], k = bhDeleteMin[b1]; Print[k]]

or as

\(b = 
      bhNew[]; \(bhInsert[
          b, #] &\) /@ {"Make", "a", "new", "empty", "heap"}; 
    Rest@NestWhileList[bhDeleteMin[b] &, 
        Null, ¬ bhEmptyQ[b] &]\)

Priority Queues II - Leftist Heaps

Priority queues are collections of items, each with an associated key. This implementation of (mergeable) priority queues uses leftist heaps.

Further details on leftist heaps can be found in Ch. 3 of
R.E. Tarjan, Data Structures and Network Algorithms, SIAM, 1983.

A leftist heap is a pair {root, order} with root denoting the root item and  order the heap order.

Symbols related to leftist heaps are prefixed by lh:

?DStruct02`lh*

Basic operations:

lhNew[L, ord] builds a new leftist heap with ordering ord starting from a list of keys  L. ord defaults to Order[#1,#2]≥0&.
lhNew[] is equivalent to lhNew[{}].

lhInsert[h, k] inserts an item with a key k into a heap.

lhDelete[h, i] deletes item i from heap h.

lhDeleteMin[h] yields a heap item with minimal key, and deletes it from heap h.

lhMin[h] returns an item of heap h with minimal key.

lhEmptyQ[h] returns True iff heap h is empty.

The first argument of lhDelete, lhDeleteMin, lhEmptyQ, lhInsert,  lhMeld, lhMin must be a symbol.

lhMeld[(Subscript[h, 1]),(Subscript[h, 2])]melds two heaps with the same ordering function; the resulting heap is heap (Subscript[h, 1]). (Subscript[h, 2]) is empty.
Both arguments of lhMeld must be symbols.

lhContents[i, opts] displays the contents of the subtree rooted at item i using an in-order traversal and a sequence of options opts, as
	lhNode[{item, key, {left child, right child}},<left subtree>, <right subtree>]

lhNode is the head of expressions collecting the contents of a node.

Possible options to lhContents are: lhShowItems, lhShowKeys, lhShowRanks, lhShowPointers -> True|False with the obvious meanings.

lhListLE[h, k] yields the list of items of heap h whose keys do not exceed k.
The first argument of lhListLE must be a symbol.

Other operations

lhKey[i] returns the key of item i.

lhRank[i] returns the rank of item i.

lhRoot[h] returns the root item i of a leftist heap h.

lhOrder[h] returns the ordering criterion of a leftist heap h.

lhOrderedQ[h][expr] returns True if the parts of expression expr are ordered w.r. to the ordering criterion of a leftist heap h.

lhOrdering[h][expr] returns the positions in  expr at which each successive element of Sort[expr, lhOrder[h]] appears.

lhChildren[i] returns the list of items that are children of item i.

lhLeftChild[i] and lhRightChild[i] give the left and the right child of item i, respectively. Null is returned when no such child exists.

Build a heap from a list of items (strings) and look at its contents:

h1 = lhNew[{"makes", "a", "new", "heap"}]; 
    lhContents[lhRoot[h1]]

Get some data related to the root item:

{#, lhKey[#], lhChildren[#]} &[lhRoot[h1]]

The deletion of an item does not remove the item but simply changes its key to Null (lazy deletion)

lhDeleteMin[h1]
lhContents[lhRoot[h1]]

Subsequent calls of  lhMin, lhDeleteMin, or lhEmptyQ remove root items with a Nulll key. Hence, the typical sequence

While queue ≠ ∅ do 
	k← min key of queue; 
	deletemin(queue);
	… 
end while

can be coded as follows:

h = lhNew[Range[3, 1, -1]]; 
    While[¬ lhEmptyQ[h], k = lhKey@lhMin[h]; lhDeleteMin[h]; 
      Print[k]]

or as

h = lhNew[Range[3, 1, -1]]; k =. ; 
    Rest@NestWhileList[(k = lhKey@lhMin[h]; lhDeleteMin[h]; k) &, 
        Null, ¬ lhEmptyQ[h] &]

Splay Trees

Splay trees are self-adjusting binary search trees due to Sleator and Tarjan. See  Ch. 4 of
R.E. Tarjan, Data Structures and Network Algorithms, SIAM, 1983, for further details.

A splay tree is implemented as a pair {root, crit}: where root is  an integer associated to the root node, and crit the ordering criterion.

Nodes are  identified by positive integers (items); each item has an associated key and pointers to its parent, left, and right child.

Symbols related splay tree operations are prefixed by st:

?DStruct02`st*

Basic operations:

stNew[crit] generates an empty splay tree with ordering  crit defaulting to  Order[#1,#2]≥0&.

stInsert[t,k]inserts a new item with key k into a tree t and returns the new item with key k if no element of t has key k, or Null.

stAccess[t,k]returns the item of t whose key is k;  Null if no such item exists in t.

stKey[i] returns the key of  item i.

stDelete[t, i] deletes item i from tree t.

the first argument of stInsert,stAccess,stDelete must be a symbol.

stRoot[t] returns the item at the root of tree t,

stRootQ[i] returns True if item i is the root of some splay tree.

stEmptyQ[t] returns True if the splay tree is empty.

stOrder[t] returns the ordering function of t.

stOrderedQ[t][e] returns True if the parts of expression e are ordered w.r. to the order of tree t.

stOrdering[t][e] gives the positions in expr at which each successive element of 
Sort[e,stOrder[t]] appears.

The contents of a splay tree can be inspected using

stContents[i, opts] displays the contents of the subtree rooted at item i using a set of options opts and a preorder traversal.

stNode is the head of the expression returned by stContents.

Possible options for stContents are:

stShowItems->True|False shows  | hides items.

stShowKeys->True|False shows  | hides item keys

stShowPointers->True|False shows | hides  item pointers.

When all options are set to True a node is displayed as

stNode[{item, key, {leftpointer, rightpointer}, parentpointer}, 
<contents of left subtree>,  <contents of right subtree>]

An empty subtree is represented by {}, and a pointer to a nonexistent item by Null.

Create a new splay tree with the default ordering (OrderedQ)

st1 = stNew[];
stInsert[st1, "Nel"]; 
    stInsert[st1, "mezzo"];
stInsert[st1, "del"];
stInsert[st1, "cammin"];

and another tree with the same keys but opposite ordering:

st2 = stNew[(Order[#1, #2] ≤ 0) &];
stInsert[st2, "Nel"]; 
    stInsert[st2, "mezzo"];
stInsert[st2, "del"];
stInsert[st2, "cammin"];

Inspect the contents of the first tree

stContents[stRoot[st1]]

Accessing items restructures the tree: the accessed item is moved to the root by means of a sequence of splay steps:

stAccess[st2, "mezzo"]; stContents[stRoot[st2]]

In order to delete the item associated to a given key execute stAccess and, if the result isn’t Null, call stDelete

stAccess[st2, "del"]
If[% =!= Null, stDelete[st2, %], $Failed]

stContents[stRoot[st2]]

Splay trees: can be joined and splitted

stSplit[t, i] splits tree t around its item i returning three trees (Subscript[t, 1]), (Subscript[t, 2]), {i} s.t. key[x] < key[i] < key[y] for every x in (Subscript[t, 1])and y in (Subscript[t, 2]). After stSplit[t, i] t is empty.

The first argument of stSplit must be a symbol.

stJoin[(Subscript[t, 1]), i, (Subscript[t, 2])] takes three trees (Subscript[t, 1]), (Subscript[t, 2]), {i} s.t. key[x] < key[i] < key[y] holds for every x in (Subscript[t, 1])and y in (Subscript[t, 2]), replaces i with their union and empties (Subscript[t, 1]), (Subscript[t, 2]).
The three arguments of stJoin must be symbols associated to trees with the same tree-order.

{ts1, ts2, ts3} = stSplit[st1, 2];

The contents of the new trees are

stContents[stRoot[#]] & /@ {ts1, ts2, ts3}

Join is the opposite of split:

tj = stJoin[ts1, ts2, ts3]; stContents[stRoot[tj]]

Other functions:

stParent[i] returns the item associated to the parent of item i.

stChildren[i] returns the list of children of item i.

stLeftChild[i] returns the item associated to the left child of item i.

stRightChild[i] returns the item associated to the right child of item i.

stMax[i] returns the item with maximum key in the subtree rooted at item i.

stMin[i] returns the item with minimum key in the subtree rooted at item i.

stPred[i] returns the item whose key precedes the key of item i.

stSucc[i] returns the item whose key follows the key of item i.

stExistsQ[i] returns True if item i represents a (nondeleted) node of some splay tree.

stLeftChildQ[i] returns True if item i is a left child.

stRightChildQ[i] returns True if item i is a right child.

stHasLeftChildQ[i] returns True if item i has a left child.

stHasRightChildQ[i] returns True if item i has a right child.

2-3 Trees

A 2-3 tree is a tree with two properties:

every internal node has two or three children;

every path from the root to a leaf (external node) has the same length.

An empty tree and a tree consisting of one node are considered as special cases of 2-3 trees.

A set of elements that can be ordered by means of some linear ordering ≺ is represented as follows:

each element is associated to a leaf, and viceversa;

each leaf has an associated Key, and leaf x is to the left of leaf y if Key[x]≺Key[y].

An internal node x has a pointer to its parent, a list of pointers to its children (two or three), and a list of pointers to leaves of minimum key, one per subtree.

Further details on the 2-3 tree data structure can be found, for instance, in Sect. 5.4 of
A.V. Aho, J.E. Hopcroft, J.D. Ullman, Data Structures and Alogirthms, Addison Wesley Pub. Co., 1983.

A 2-3 tree is represented by a list with two elements {root, crit}:  root is a positive integer identifying the root item and crit is the ordering criterion.

Symbols related to 2-3 trees are prefixed by t23:

?DStruct02`t23*

Basic operations:

t23New[crit] generates an empty 2-3 tree with ordering crit defaulting to Order[#1,#2]≥0&.

t23Insert[t, k] inserts a new item with key k into tree t, and returns the new item with key k if no element of t has key k,  or Null.

t23Access[t, k] returns the item of tree t whose key is k; Null is returned if no such item exists in t.

t23Key[i] returns the key of item i.

t23Delete[t, i] deletes item i from tree t.

the first argument of t23Insert,t23Access,t23Delete must be a symbol.

t23Root[t] returns the root item  of  tree t (Null if t is empty).

t23EmptyQ[t] yields True iff tree t is empty.

t23RootQ[t] returns True iff item i is the root of some 2-3 tree.

t23Order[t] returns the ordering criterion of tree t.

t23OrderedQ[t][expr] returns True if the parts of expression expr are ordered w.r. to the ordering of tree t.

t23Ordering[t][expr] gives the positions in expr at which each successive element of
Sort[expr, t23Order[t]] appears.

The contents of a 2-3 tree can be inspected with

t23Contents[i, opts] displays the contents of the subtree rooted at item i using a set of options opts and a preorder traversal. Possible options are: 
t23ShowItems ->True|False, t23ShowKeys ->True|False, t23ShowMins ->True|False, t23ShowPointers ->True|False, t23OneItem ->True|False.

When every options is set to True internal nodes are displayed as 
	t23Node[{item, <i1, i2,...>,{p1, p2, ...}, pptr}, subtree1,  subtree2,...] 
and a leaf as 
	t23Leaf[item, key, pptr]
pptr is the parent item (Null for the root node);
{p1, p2, ...} is the list of items that are children of item;
<i1, i2,...> are the items of minimum key in the first subtree (i1), in the second one (i2), etc.

Create a new tree and insert something into it:

t1 = t23New[];
t23Insert[t1, "three"]; t23Insert[t1, "four"]; 
    t23Insert[t1, "five"]; t23Insert[t1, "six"];

t23Contents uses the following options

Options[t23Contents]

Contents of t1:

t23Contents[t23Root[t1], t23ShowMins -> True, 
      t23ShowPointers -> True]

In order to delete the leaf with key "six" we need the corrisponding item

i = t23Access[t1, "six"]
t23Delete[t1, i];
t23Contents[t23Root[t1], t23ShowMins -> True, 
      t23ShowPointers -> True]

t23Pred[i] and t23Succ[i] return the predecessor and the successor of item i of some 2-3 tree, respectively (Null is returned if i has no predecessor or successor).

{t23Pred[3], t23Succ[3]}
{t23Pred[4], t23Succ[1]}

t23Max[i] and t23Min[i] return the items of maximum, resp. minimum key belonging to the subtree rooted at item i.

t23Mins[i] returns the list of items of minimum key in each subtree rooted at item i.

{t23Min[2], t23Max[2], t23Mins[2]}

t23Parent[i] and t23Children[i] return the parent and the list of children of item i of some 2-3 tree, respectively (Null is returned if i has no parent).

t23LeftSibling[i] and t23RightSibling[i] return the left and right sibling of item i.

t23FirstChildQ[i] and t23LastChildQ[i] return True iff item i is a first, resp. last, child.

{t23Parent[4], t23Children[2]}
{t23LeftSibling[3], t23RightSibling[3]}

t23NodeQ[i] and t23LeafQ[i] return True if item i is an internal node or a leaf of some 2-3 tree.

t23ExistsQ[i] returns True iff item i is a node of some 2-3 tree.