Finding last element in linked structure heap

Question

I was wondering how you would go about finding the furthest element in a linked structure implementation of a heap and the root element. I want to be able to Enque and Deque elements.

Some clarification: what I meant was lets say you have a linked structure making up a max heap (root element has the largest value). Your tree would have an element somewhere at the very bottom which you would insert after or remove depending on if you are enqueing or dequeing. How do you determine that element? and how do you determine the root node of the tree? (the top one)

Answer 1

I'm not completely positive this is what you are asking for, but this is one way of pointing to the last element of a singly-linked list:

T *p = NULL, *q = NULL;  // q follows p by one node
p = root;
while (p)
{
    q = p;
    p = p -> next;
}

// q now points to last node

Answer 2

Maybe something like this ?

struct node {
  node *parent;
  node *children[2];
  int data; //or whatever else you want
};

struct heap {
  node *root;
  node *last;
};

This is a lot trickier to implement then just using an array though. Here is a hypothetical add

void add(struct heap* h, int d)
{
  node* add = malloc(sizeof(node));
  add->data = d;
  node* current = h->root;
  while(current->children[1]) current = current->children[1];
  current->children[1] = add;
  add.parent = current;
  add.children[0] = NULL;
  add.children[1] = NULL; 
  h.last = add;
  percolate_up(h);
}

Something like that.

Answer 3

The normal method for adding something to a heap structure is to start at the root and "walk" the tree to find the place where the new element goes. When you find where it goes, you put it there, and if that means replacing what's already in that spot, then you take the previous value and keep walking down to find where it goes. Repeat until you hit a leaf, then add whatever value you're "carrying" as the appropriate child of that leaf.

Suppose your new value was 5 and the root node of the heap held a 10. 5 clearly goes below 10, so you look at the children of 10. Suppose they're 8 and 7. Both are larger than 5, so pick one (how you pick one depends on whether you're trying to keep the heap balanced). Suppose you pick 7, and it has children 3 and 4. 5 goes below 7 but above 3 or 4, so you replace, say, the 4 with 5, then look at that node's children to see where to put the 4. Suppose it has no children, you can just add a new leaf containing 4.

As for your question about how you find the root -- generally the root is the only pointer to the tree that you keep. It's your starting point for all operations. If you started somewhere else, I suppose you could navigate up to the root, but I'd question why.