Article 109 - Heap Implementation

This article discusses the implementation of a Heap Structure.

For information about the Heap Structure, see Article 31 - Programming Data Structures.

To program a Heap, we need to understand the interface of a Heap.

Interface

  • Add Entry
  • Get Min

Implementation

To make the implementation more challenging, we will swap nodes instead of values.

The following is the structures used for the Heap.

typedef struct Node{
    struct Node * parent;
    struct Node * leftChild;
    struct Node * rightChild;
    int depth;
    int content;
    int package;
}

A function that creates a new node, will be useful for initializing values.

Node * newNode( int content, int package = 0 ){
    Node * newNode = (Node *)malloc( sizeof( Node ) );

    if( newNode ){
        newNode->parent = 0;
        newNode->leftChild = 0;
        newNode->rightChild = 0;
        newNode->depth = 0;
        newNode->content = content;
        newNode->package = package;
    }

    return newNode;
}

A function that adds an entry to the heap.

int addNode( Node ** heap, int content, int package = 0 ){
    Node * newNode;
    Node * nodePointer;
    Node * swapParent;
    Node * swapLeftChild;
    Node * swapRightChild;
    int swapDepth;

    if( !heap ){
        return -1;
    }

    newNode = newNode( content, package );

    if( !newNode ){
        return -2;
    }

    newNode->content = content;

    //if heap is null, assign and return new node
    if( !*heap ){
        *heap = newNode;

        return 0;
    }

    //append new node at the end of the pseudo complete tree
    for( nodePointer = *heap; ; ){
        //if left child does not exist, assign to left child
        if( !nodePointer->leftChild ){
            nodePointer->leftChild = newNode;
            newNode->parent = nodePointer;
            nodePointer->depth++;
            break;
        }
        else if( !nodePointer->rightChild ){
            //assign as right child (left child exists)
            nodePointer->rightChild = newNode;
            newNode->parent = nodePointer;
            nodePointer->depth++;
            break;
        }
        else if( nodePointer->leftChild->depth == 
            nodePointer->rightChild->depth ){
            //both childs have same depths, go left
            nodePointer = nodePointer->leftChild;
        }
        else{
            //left child is deeper, go right
            nodePointer = nodePointer->rightChild;
        }
    }

    //swim operation, required to preserve heap's integrity
    for( nodePointer = newNode; ; ){
        if( !nodePointer->parent ){ //root has no parent
            break;
        }

        if( nodePointer->content > nodePointer->parent->content ){
            swapParent = nodePointer->parent;
            swapLeftChild = nodePointer->leftChild;
            swapRightChild = nodePointer->rightChild;
            swapDepth = nodePointer->depth;

            //determine which side of parent this node belongs to
            if( swapParent->leftChild == nodePointer ){
                nodePointer->rightChild = swapParent->rightChild;
                nodePointer->leftChild = swapParent;
            }
            else{
                nodePointer->leftChild = swapParent->leftChild;
                nodePointer->rightChild = swapParent;
            }

            nodePointer->parent = swapPointer->parent;
            nodePointer->depth = swapPointer->depth;

            //fix parent
            swapParent->parent = nodePointer;
            swapParent->leftChild = swapLeftChild;
            swapParent->rightChild = swapRightChild;
            swapParent->depth = swapDepth;

            //fix grandparent, unless root
            if( nodePointer->parent ){
                if( nodePointer->parent->leftChild = swapParent ){
                    nodePointer->parent->leftChild = nodePointer;                    
                }
                else{
                    nodePointer->parent->rightChild = nodePointer;
                }
            }
            else{
                *heap = nodePointer;
            }
        }
        else{
            break;
        }
    }

    return 0;
}

A function that retrieves the minimum entry and removes it from the heap.

int getTop( Node ** heap, int * content, int * package = 0 ){
    Node * newNode;
    Node * nodePointer;
    Node * swapParent;
    Node * swapLeftChild;
    Node * swapRightChild;
    int * swapDepth;

    if( !heap ){
        return -1;
    }

    if( !content ){
        return -1;
    }

    if( !*heap ){
        return -2;
    }

    //top is entry we retrieve
    *content = (*heap)->content;
    
    if( package ){
        *package = (*heap)->package;
    }
    
    swapLeftChild = (*heap)->leftChild;
    swapRightChild = (*heap)->rightChild;   

    //find last node of pseudo complete binary tree
    for( nodePointer = *heap; ; ){
        //if left child does not exist, remove this node
        if( !nodePointer->leftChild ){
            //this case represents root node
            free( nodePointer );
            *heap = 0;
            return 0;
        }
        else if( !nodePointer->rightChild ){
            //no right child
            //go left is extra call, just swap left *leaf* child
            nodePointer->depth--; //decrement first
            nodePointer = nodePointer->leftChild;
            break;
        }
        else if( nodePointer->leftChild->depth == 
            nodePointer->rightChild->depth ){
            //both childs have same depths, go right
            nodePointer = nodePointer->rightChild;
            nodePointer->depth--;
        }
        else{
            //left child is deeper, go left
            nodePointer = nodePointer->leftChild;
            nodePointer->depth--;
        }
    }

    //swap node (with top)
     *heap = nodePointer;
    (*heap)->leftChild = swapLeftChild;
    (*heap)->rightChild = swapRightChild;

    //sink new top to appropriate position to preserve heap
    for( nodePointer = *heap; ; ){
        if( !nodePointer->leftChild ){
            //leaf node no more sinking
            break;
        }
        else if( !nodePointer->rightChild ){
            //no right child, compare with left child

            if( nodePointer->leftChild->content > 
                nodePointer->content ){
                //swap left child with current node

                swapParent = nodePointer->parent;
                swapLeftChild = nodePointer->leftChild;
                swapRightChild = nodePointer->rightChild;
                swapDepth = nodePointer->depth;

                //move node to leftchild
                nodePointer->parent = swapLeftChild;
                nodePointer->leftChild = swapLeftChild->leftChild;
                nodePointer->rightChild = swapLeftChild->rightChild;
                nodePointer->depth = swapLeftChild->depth;
                //no grandchildren to update (in this case)

                //update grandparent, if any
                if( swapParent ){
                    if( swapParent->leftChild == nodePointer ){                       
                        swapParent->leftChild = swapLeftChild;
                    }
                    else{
                        swapParent->rightChild = swapLeftChild;
                    }

                    nodePointer->parent = swapLeftChild;
                }
                else{
                    *heap = swapLeftChild;
                }

                //update left child as parent
                swapLeftChild->parent = swapParent;
                swapLeftChild->leftChild = nodePointer;
                swapLeftChild->rightChild = swapRightChild;
                swapLeftChild->depth = swapDepth;
            }
        }
        else{
            if( nodePointer->leftChild->content > 
                nodePointer->rightChild->content ){
                //left child is greater, check with parent
                if( nodePointer->leftChild->content > 
                    nodePointer->content ){
                    //swap with left child

                    swapParent = nodePointer->parent;
                    swapLeftChild = nodePointer->leftChild;
                    swapRightChild = nodePointer->rightChild;
                    swapDepth = nodePointer->depth;

                    //swap current node with left child
                    nodePointer->parent = swapLeftChild;
                    nodePointer->leftChild = swapLeftChild->leftChild;
                    nodePointer->rightChild = 
                        swapLeftChild->rightChild;
                    nodePointer->depth = swapLeftChild->depth;

                    //update grandparent, if any
                    if( swapParent ){
                        if( swapParent->leftChild == nodePointer ){                       
                            swapParent->leftChild = swapLeftChild;
                        }
                        else{
                            swapParent->rightChild = swapLeftChild;

                        }
                    }
                    else{
                        *heap = swapRightChild;
                    }

                    swapLeftChild->parent = swapParent;
                    swapLeftChild->leftChild = nodePointer;
                    swapLeftChild->rightChild = swapRightChild;
                    swapLeftChild->depth = swapDepth;
                }
            }
            else{
                //right child is greater or equal, check with parent
                if( nodePointer->rightChild->content > 
                    nodePointer->content ){
                    //swap with right child

                    swapParent = nodePointer->parent;
                    swapLeftChild = nodePointer->leftChild;
                    swapRightChild = nodePointer->rightChild;
                    swapDepth = nodePointer->depth;

                    //swap current node with right child
                    nodePointer->parent = swapRightChild;
                    nodePointer->leftChild = 
                        swapRightChild->leftChild;
                    nodePointer->rightChild = 
                        swapRightChild->rightChild;
                    nodePointer->depth = swapRightChild->depth;

                    //update grandparent, if any
                    if( swapParent ){
                        if( swapParent->leftChild == nodePointer ){                       
                            swapParent->leftChild = swapRightChild;
                        }
                        else{
                            swapParent->rightChild = swapRightChild;

                        }
                    }
                    else{
                        *heap = swapRightChild;
                    }

                    swapRightChild->parent = swapParent;
                    swapRightChild->leftChild = swapLeftChild;
                    swapRightChild->rightChild = nodePointer;
                    swapRightChild->depth = swapDepth;
                }
            }            
        }        
    }

    return 0;
}

Comments (0)

Post a comment

  • Name:
  • Post:
  • Challenge:

Register or login to post comments easier.


Vantasy World Copyright 2011 - 2017. Vantasy World is a project developed by Vantasy Online. Privacy Policy.