Linking Two Multi-Dimensional arrays using pointers

Question

I need to basically merge a Binary Heap, and Linear Probing Hashtable to make a "compound" data structure, which has the functionality of a heap, with the sorting power of a hashtable. What I need to do is create 2 2 dimension arrays for each data structure (Binary Heap, and Hash) then link them to each other with pointers so that when I change things, such as deleting a value in the Binary Heap, it also gets deleted in the Hash table. Therefore, I need to have one row of the Heap array pointing from the Heap to the Hastable, and one row of the hashtable array pointing from the hashtable to the heap. Any help with just generally how to link these two together is appreciated, after some ideas I can probably figure it out, just having trouble getting started.

Answer 1

Why bother with the links?

You have two associative structures just duplicate any operation on one to the other (ensuring that if one operation excepts you either crash the whole thing or leave the object in a valid state if you care about such things)

Unless you can make use of the structure of one to help you with the other (and I don't see how you can since either one can entirely rearrange it's internal state on any modification operation) this is just as effective and much simpler.

Of course this means that the O() cost of any modification operation is the cost of the most expensive and memory costs are doubled but that is true of the original plan unless their is some trick I'm missing.

Answer 2

Create a container that contains both, with accessor functions/methods (depending on your language of implementation) that performs all the operations required of your algorithm.

IE: Delete from container: does a delete from Binary and from hash.

Add to container: adds to binary and to hash.

EDIT: Oh, an assignment - fun! :)

I'd do this: still implement a container. But, instead of using a standard library for btree/hash, implement them like this: Make a type that can be put in your data member that has a pointer to the BTree node and the Hashtable Node that the data element lives in.

To delete a data element, given a pointer to it, you can perform the delete algorithm on a btree (navigate to parent from node pointer, delete child (left or right), restructure tree) and on the hash table (delete from hash list). When adding a value, perform the add algorithm on btree and hash, but be sure you update the node pointers in the data before you return.

Some pseudocode (I'll use C, but i'm not sure what language your using): typedef struct { BTreeNode* btree HashNode* hash } ContianerNode;

to put data in your container:

typedef struct
{
    ContainerNode node;
    void* data; /* whatever the data is */
} Data;

a BTreeNode has something like:

typedef struct _BTreeNode
{
    struct _BTreeNode* parent;
    struct _BTreeNode* left;
    struct _BTreeNode* right;
} BTreeNode;

and a HashNode has something like:

typedef struct _HashNode
{
    struct _HashNode* next;
} HashNode;
/* ala singly linked list */

and your BTree would be a pointer to a BTreeNode and your hastable would be an array of pointers to HashNodes. Like this:

typedef struct
{
    BTreeNode* btree;
    HashNode* hashtable[HASHTABLESIZE];
} Container;

void delete(Container* c, ContainerNode* n)
{
    delete_btree_node(n->btree);
    delete_hashnode(n->hash);
}

ContainerNode* add(Container* c, void* data)
{
    ContainerNode* n = malloc(sizeof(ContainerNode));
    n->btree = add_to_btree(n);
    n->hash = add_to_hash(n);
}

I'll let you complete those other functions (can't do the whole assignment for you ;) )