Code automation depending on result

[adam2016]

Hi guys,

I'm trying to implement my own heap for the very first time, I have been told that heaps are normally implemented using a vector or an array but it can be done using a linked binary tree, anyway most of the code online just gives an example of the array implementation so as a challenge I wanted to try and write an implementation using a linked binary tree structure but I have run into a problem,

first I check to see if the roots left child == NULL if it doesn't I check if the roots right child == NULL, if both are taken by an element I then check the roots grandparents for an empty node, I first start to check if either of the left grandchildren == NULL if they both are taken I go right instead of left,this works( well on paper ) but after the roots grandchildren are all populated the tree->left->left != NULL && tree->left->right != NULL will be invalid as this condition will now always be true,

so what I would like to do is append another ->left to the tree->left->left and keep doing so until I find a descendent that has free children, is this even possible?

template<class T>
class Node{

public:
    T element;
    Node<T>* parent;
    Node<T>* left;
    Node<T>* right;

    Node(){}
};


template<class T>
class Heap{

public:

    Heap(){}

    Node<T>* addNode(Node<T>* tree,T el,Node<T>* parent = NULL){

       if(tree == NULL){

        Node<T>* newNode = new Node<T>;
        newNode->element = el;
        newNode->parent = parent;
        newNode->left = NULL;
        newNode->right = NULL;
        return newNode;
       }
       if(el > tree->element){
         
         if(tree->left == NULL){
            tree->left = addNode(tree->left,el,tree);
         }
         else if(tree->right == NULL){
            tree->right = addNode(tree->right,el,tree);
         }
         
         // function to check if all children root nodes are NULL
         while(true){
                
         int i = 2;
         
         if(tree->left->left != NULL && tree->left->right != NULL){
            tree->right = addNode(tree->right,el,tree);
            break;
         }else{
            tree->left = addNode(tree->left,el,tree);
            break;
         }
         }
         ++i;
       }
       // insert to last if less
       return tree;
    }
};

thanks

[Duthomhas]

You need to rethink how the tree is populated.

A heap should have a very strict structure. For example:

  • LEFT cannot be null if RIGHT is not null
  • PARENT item's value < any CHILD item's value

You also need a function to enforce the rules — in other words, to modify the structure (recursively swapping nodes) to fix it.

Insertion is then just adding the node somewhere at the bottom of the heap, then applying that function to fix the constraints.


For a case study to look at, check out how the heap sort works:
http://www.cplusplus.com/faq/sequences/sequencing/sort-algorithms/heapsort/
In particular, notice how the heap property is maintained with the “push down/sink” function.

Hope this helps.

[dutch]

This is insanely inefficient, but I assume you know that. The hideous waste of space (three pointers per node!) and how heaps perfectly fit arrays/vectors (since the trees are essentially complete) is why heaps are not implemented this way.

To make insertion into the tree more efficient you could maintain a list of "unused" bottom nodes (ones with at least the right pointer unused). Keep a pointer to the 'head' and 'tail' of this list and use the 'right' pointers as 'next' pointers. Then to insert, you attach the new node to the 'head' of that list (to its 'left' pointer if unused, in which case the node stays in the 'unused' list; otherwise to its 'right', in which case the node is removed from the 'unused' list). Then you need to "bubble up" the new node to its correct position. Then you need to add whatever node ended up in the original insertion position to the 'tail' of the 'unused' list.

[adam2016]

Thanks Duthomhas

I'm actually trying to store this heap data structure in a proper linked binary tree, I have an idea how a heap works but can't seem to implement it without using a vector or an array

@Dutch very true again this code will not work, but the reason I keep three pointers is for ease of traversing the tree, for example I would not be able to get the depth of a particular node without the link to it's parent.

To make insertion into the tree more efficient you could maintain a list of "unused" bottom nodes (ones with at least the right pointer unused). Keep a pointer to the 'head' and 'tail' of this list and use the 'right' pointers as 'next' pointers. Then to insert, you attach the new node to the 'head' of that list (to its 'left' pointer if unused, in which case the node stays in the 'unused' list; otherwise to its 'right', in which case the node is removed from the 'unused' list). Then you need to "bubble up" the new node to its correct position. Then you need to add whatever node ended up in the original insertion position to the 'tail' of the 'unused' list.

very good idea but I haven't the first idea how to implement that but I'll give it a shot :)