Max Heap C++

Binary heap. Array-based internal representation.


Heap is a binary tree and therefore can be stored inside the computer using links. It gives various benefits; one of them is the ability to vary number of elements in a heap quite easily. On the other hand, each node stores two auxiliary links, which implies an additional memory costs. As mentioned above, a heap is a complete binary tree, which leads to the idea of storing it using an array. By utilizing array-based representation, we can reduce memory costs while tree navigation remains quite simple


As for the heapsort algorithm, array-based implementation is kind of native.


Mapping heap to array


A heap is stored in array level by level. The topmost level contains root only. It is mapped to the first element of an array (with index 0). Root's children are mapped to the second and third elements and so on. A heap is a complete binary tree, which guarantees, that heap's nodes take up places in the array compactly, making the mapping quite efficient.

///////////FILE 1 //////////////// #ifndef BINARYHEAP_H #define BINARYHEAP_H class BinaryHeap { int * data; int heapSize; int arrayMaxSize; public: BinaryHeap(int size) { data = new int[size]; arrayMaxSize=size; heapSize =0; } BinaryHeap(int size,int *array) { data = array; arrayMaxSize=size; heapSize =size; } virtual ~BinaryHeap() { delete[] data; } void heapify(int *arr,int index); int getLeftChild(int index); int getRightChild(int index); int getParent(int index); void printHeap(); void buildHeap(); protected: private: }; #endif // BINARYHEAP_H ////////////////FILE 2//////////// #include "binaryheap.h" #include<iostream> using namespace std; void BinaryHeap::heapify(int *arr,int index) { if(index>heapSize || index> arrayMaxSize) { cout<<"The index you have provide is incorrect"<<endl; return; } int maxindex = index; int left= getLeftChild(index); int right = getRightChild(index); if(left<heapSize && arr[left]>arr[index]) { maxindex = left; } if(right<heapSize && arr[right]>arr[maxindex]) { maxindex=right; } if(index != maxindex) { int temp = arr[index]; arr[index] = arr[maxindex]; arr[maxindex] = temp; heapify(arr,maxindex); } return; } int BinaryHeap::getLeftChild(int index) { return (2*index+1); } int BinaryHeap::getRightChild(int index) { return (2*index+2); } int BinaryHeap::getParent(int index) { return int((index-1)/2); } void BinaryHeap::buildHeap() { if(heapSize<=0) { return; } for(int i=(heapSize-2)/2;i>=0;i--) { cout<<" :"<<i; heapify(data,i); } } void BinaryHeap::printHeap() { int i=0; cout<<" "<<endl; while(i<heapSize) { cout<<*(data+i)<<", "; i++; } cout<<" "<<endl; } //////////FILE 3 DRIVER - MAIN///////////////// #include<iostream> #include "binaryheap.h" using namespace std; #define SIZE 5 int main() { int *array = new int[SIZE]; int i =0; cout<<" enter the data"<<endl; while(i<SIZE) { cin>>array[i]; i++; } i=0; /* while(i<10) { cout<<" "<<array[i]; i++; }*/ BinaryHeap* heap = new BinaryHeap(SIZE,array); heap->printHeap(); heap->buildHeap(); heap->printHeap(); return 1; }

Nearest common Ancestor Given a binary tree(not a BST), you need to find the Nearest common ancestor of the two given values.

/* InOrder Traversal Left ==> ROOT ==> RIGHT , hence the NCA of 2 nodes should be inbetween the 2 nodes in the vector. PostOrder traversal LEFT ==> RIGHT ==> ROOT , hence the NCA is the leftmost in postOrder vector of all the elements found inbetween in INOrder vector */ int nca(BinaryTreeIntNode* node,int n1,int n2) { if(node == NULL) { return -1; } int nca = -1; std::vector* vectInorder = new std::vector(); std::vector* vectPost = new std::vector(); InOrderRecVector(node,vectInorder);//get the inOrder traversal in a Vector postOrderRecVector(node,vectPost);//get the postOrder traversal in a Vector int tempIndex = 0; int index1 = std::find(vectInorder->begin(),vectInorder->end(),n1) - vectInorder->begin(); int index2 = std::find(vectInorder->begin(),vectInorder->end(),n2) - vectInorder->begin(); int i = (index1>index2?index1:index2); int j = (index1>index2?index2:index1); for(i; i >= j;i--) { tempIndex = std::find(vectPost->begin(),vectPost->end(),vectInorder->at(i))-vectPost->begin(); nca = nca>tempIndex?nca:tempIndex; } if(nca==-1) { return -1; } cout<<" The NCA of "<< n1 <<" and "<< n2<< " = "<at(nca)<at(nca); }

Diameter of a binary tree

Given a binary tree you need to find the diameter of the binary tree. Diameter is defined as the maximum distance possible between any two nodes in the binary tree (It is implicit that the nodes will be the leaf nodes of the tree).

int LintkedIntTree::diameter(BinaryTreeIntNode* node) { if(node == NULL) { return 0; } int hl=heightRec(node->left); int hr=heightRec(node->right); int ld=diameter(node->left); int lr=diameter(node->right); return (ld>lr?ld:lr)>(hl+hr+1)?(ld>lr?ld:lr):(hl+hr+1); }

Brief summary of PostOrder traversal(Recursive and Non-Recursive),C++

PostOrder traversal: Is a method of visiting all nodes of a Binary tree where the Left child  of a node is visited first then the Right child of the node and in the end the Root(node). The term Post refers to the position of the ROOT in the traversal result. The ROOT of the tree is the last element in the result of this traversal.

deque(Pronunciation deck) is a data structure available in the C++ STL. Its a queue where insertions and deletions are done at both the ends.

/* Wrapper function to call the recursive and non recursive methods. */ void LintkedIntTree::postOrder(bool isRecursive) { if(isRecursive == true) { postOrderRec(root); }else { StacktNode* temp = new StacktNode(root,NULL); StackInt* stack=new StackInt(temp,1); postOrderNonRecDeck(stack); stack=new StackInt(temp,1); cout<<"\n POST Order COLOURING\n"; postOrderNonRecColour(stack); } return; } /* Recursive implementation: Logic: the LeftChild is visited first the Right child next now its the root Print it out. */ void LintkedIntTree::postOrderRec(BinaryTreeIntNode* node) { if(node == NULL) { return; }else { postOrderRec(node->left); postOrderRec(node->right); cout<<" "<<node->data; return; } } /* NON Recursive implementation: Logic: push the root onto the stack while Stack not empty pop the node push_front onto a deque(is a datastructure in which the insertions can be done either in the front or back, push_front inserts from the back of the deque) push the left child(we push the left child first as we are populating the traversal from behind and we need the right child first) push the right child end while */ void LintkedIntTree::postOrderNonRecDeck(StackInt* stack) { std::deque<int>* deck= new deque<int>(); if(stack == NULL) { return; } while(!stack->isEmpty()) { StacktNode* temp = stack->pop(); if(temp==NULL) { continue; } BinaryTreeIntNode* t = temp->node; temp->~StacktNode(); deck->push_front(t->data); if(t->left!= NULL) { StacktNode* l= new StacktNode(t->left,NULL); stack->push(l); } if(t->right != NULL) { StacktNode* r = new StacktNode(t->right,NULL); stack->push(r); } } deque<int>::iterator it; it = deck->begin(); int x =deck->size(); cout<<"DECK SIZE = "<<x <<endl; while(it!=deck->end()) { cout<<" "<<*it++; } }

A brief summary of Binary Tree PreOrder (Recursive and Non - Recursive) Implementaion

PreOrder traversal: Is a method of visiting all nodes of a Binary tree where the Root of the given node is traversed first followed by the Left child and then the Right child of the node. The term Pre refers to the position of the ROOT in the traversal result. The ROOT of the tree is the first element in the result of this traversal.

The logic involved in the implementation of the solution is in the comments of the below code.
Just one point which i need to mention about solving recursive problems in a non recursive method involves
two indispensable ingredients for the solution u cook i) Stack, ii) While Loop.

/* Wraper function to call either of the PreOrder implementations, Recursive/Non-Recursive. Function accepts a boolean and whe ever its true the recursive method is invoked else non-recursive method. */ void LintkedIntTree::preOrder(bool isRecursive) { if(isRecursive==true) { this->preOrderRec(root); } else{ StacktNode* temp = new StacktNode(root,NULL); StackInt* stack = new StackInt(temp,1); this->preOrderNonRec(stack); } return; } /* Recursive method is simple if understand the recursive paradigm. Currently the function just prints the traversal result, An vector can be used to store the traversal and return the result. Logic: the node being visited is printed out first later its left child is passesd and then the right child. */ void LintkedIntTree::preOrderRec(BinaryTreeIntNode* node) { if(node == NULL){return;} cout<<" "<<node->data; preOrderRec(node->left); preOrderRec(node->right); return; } /* When ever we are asked to implementat a Recursively solvable problem with a non Recursive solution, Two things will become in dispensable i) Stack and ii) While loop. Logic: Push the Root on the Stack. While the stack is not empty pop the node print the value if right child not NULL push right if left child not null push the left loop end. Note we push the right child first as Stack is a LIFO structure, hence left child is oped out first by pusing right followed by left child. */ void LintkedIntTree::preOrderNonRec(StackInt* stack) { while(!stack->isEmpty()) { StacktNode* temp = stack->pop(); if(temp == NULL) { continue; } else { cout<<" "<<temp->node->data; if(temp->node->right!= NULL) { StacktNode* right = new StacktNode(temp->node->right,NULL); stack->push(right); } if(temp->node->left!= NULL) { StacktNode* left = new StacktNode(temp->node->left,NULL); stack->push(left); } } temp->~StacktNode(); } return; }

A brief summary Binary Tree, C++ implementation

This is a NON Generic implementation(Templates are not Used )

Below are the two header files which defines the class for a Binary tree which holds integer data.

BinaryTreeIntNode.h file defines how the the nodes of the tree are implemented, BinaryTreeIntNode.cpp

has the corresponding member functions implementation. 

LintkedIntTree.h file defines the structure of a Binary tree and the operation on the Binary tree,

LintkedIntTree.cpp has the corresponding implementations of member functions.

For more information on Trees visit:

http://abriefsummaryofeverything.blogspot.com/2011/08/trees-and-binary-treesdraft-version.html
/*################################################################################################################################ FILE:BinaryTreeIntNode.h Author:Thejas ################################################################################################################################*/ #ifndef BINARYTREEINTNODE_H #define BINARYTREEINTNODE_H using namespace std; class BinaryTreeIntNode { public: int data; BinaryTreeIntNode* left; BinaryTreeIntNode* right; BinaryTreeIntNode(); BinaryTreeIntNode(int element,BinaryTreeIntNode* leftNode,BinaryTreeIntNode* rightNode); BinaryTreeIntNode(int element); virtual ~BinaryTreeIntNode(); protected: private: }; #endif // BINARYTREEINTNODE_H /*################################################################################################################################# FILE:LintkedIntTree Author:Thejas #################################################################################################################################*/ #ifndef LINTKEDINTTREE_H #define LINTKEDINTTREE_H #include "BinaryTreeIntNode.h" #include "../stackint.h" class LintkedIntTree { public: LintkedIntTree(); LintkedIntTree(BinaryTreeIntNode* node,int size); void preOrder(bool isRecursive); void preOrderRec(BinaryTreeIntNode* node); void preOrderNonRec(StackInt* stack); void postOrder(bool isRecursive); void postOrderRec(BinaryTreeIntNode* node); void postOrderNonRecDeck(StackInt* stack); void postOrderNonRecColour(StackInt* stack); void inOrder(bool isRecursive); void InOrderRec(BinaryTreeIntNode* node); void InOrderNonRecColour(StackInt* stack); int height(bool isRecursive); int heightRec(BinaryTreeIntNode* node); int heightNonRec(StackInt* stack); virtual ~LintkedIntTree(); protected: private: BinaryTreeIntNode* root; int treeSize; }; #endif // LINTKEDINTTREE_H

/*################################################################################################################################ FILE:BinaryTreeIntNode.cpp Author:Thejas ################################################################################################################################*/ #include "../include/BinaryTreeIntNode.h" #include<iostream> BinaryTreeIntNode::BinaryTreeIntNode() { data=0; left=NULL; right=NULL; } BinaryTreeIntNode::BinaryTreeIntNode(int element,BinaryTreeIntNode* leftNode,BinaryTreeIntNode* rightNode) { data=element; left=leftNode; right=rightNode; } BinaryTreeIntNode::BinaryTreeIntNode(int element) { data=element; left=NULL; right=NULL; } BinaryTreeIntNode::~BinaryTreeIntNode() { //dtor } /*################################################################################################################################ FILE:LintkedIntTree.cpp Author:Thejas ################################################################################################################################*/ #include "../include/LintkedIntTree.h" #include<iostream> #include <deque> LintkedIntTree::LintkedIntTree() { root=NULL; } LintkedIntTree::~LintkedIntTree() { //dtor } LintkedIntTree::LintkedIntTree(BinaryTreeIntNode* node,int size) { treeSize= size; root = node; } void LintkedIntTree::preOrderRec(BinaryTreeIntNode* node) { if(node == NULL){return;} cout<<" "<<node->data; preOrderRec(node->left); preOrderRec(node->right); return; } void LintkedIntTree::preOrder(bool isRecursive) { if(isRecursive==true) { this->preOrderRec(root); } else{ StacktNode* temp = new StacktNode(root,NULL); StackInt* stack = new StackInt(temp,1); this->preOrderNonRec(stack); } return; } void LintkedIntTree::preOrderNonRec(StackInt* stack) { while(!stack->isEmpty()) { StacktNode* temp = stack->pop(); if(temp == NULL) { continue; } else { cout<<" "<<temp->node->data; if(temp->node->right!= NULL) { StacktNode* right = new StacktNode(temp->node->right,NULL); stack->push(right); } if(temp->node->left!= NULL) { StacktNode* left = new StacktNode(temp->node->left,NULL); stack->push(left); } } temp->~StacktNode(); } return; } void LintkedIntTree::postOrder(bool isRecursive) { if(isRecursive == true) { postOrderRec(root); }else { StacktNode* temp = new StacktNode(root,NULL); StackInt* stack=new StackInt(temp,1); postOrderNonRecDeck(stack); stack=new StackInt(temp,1); cout<<"\n POST Order COLOURING\n"; postOrderNonRecColour(stack); } return; } void LintkedIntTree::postOrderRec(BinaryTreeIntNode* node) { if(node == NULL) { return; }else { postOrderRec(node->left); postOrderRec(node->right); cout<<" "<<node->data; return; } } void LintkedIntTree::postOrderNonRecDeck(StackInt* stack) { std::deque<int>* deck= new deque<int>(); if(stack == NULL) { return; } while(!stack->isEmpty()) { StacktNode* temp = stack->pop(); if(temp==NULL) { continue; } BinaryTreeIntNode* t = temp->node; temp->~StacktNode(); deck->push_front(t->data); if(t->left!= NULL) { StacktNode* l= new StacktNode(t->left,NULL); stack->push(l); } if(t->right != NULL) { StacktNode* r = new StacktNode(t->right,NULL); stack->push(r); } } deque<int>::iterator it; it = deck->begin(); int x =deck->size(); cout<<"DECK SIZE = "<<x <<endl; while(it!=deck->end()) { cout<<" "<<*it++; } } void LintkedIntTree::postOrderNonRecColour(StackInt* stack) { if(stack == NULL) { return; } while(!stack->isEmpty()) { StacktNode* temp = stack->pop(); if(temp == NULL) { continue; } BinaryTreeIntNode* n = temp->node; if(n==NULL) { continue; } if(temp->colour == 0) { StacktNode* t = new StacktNode(n->right,NULL); temp->colour = 1; stack->push(temp); stack->push(t); t=new StacktNode(n->left,NULL); stack->push(t); } else { cout<<" "<<n->data; } } } void LintkedIntTree::inOrder(bool isRecursive) { if(isRecursive == true) { InOrderRec(root); }else { StacktNode* temp = new StacktNode(root,NULL); StackInt* stack=new StackInt(temp,1); InOrderNonRecColour(stack); } } void LintkedIntTree::InOrderRec(BinaryTreeIntNode* node) { if(node == NULL) { return; } InOrderRec(node->left); cout<<" "<<node->data; InOrderRec(node->right); return; } void LintkedIntTree::InOrderNonRecColour(StackInt* stack) { if(stack == NULL) { return; } while(!stack->isEmpty()) { StacktNode *temp = stack->pop(); if(temp== NULL || temp->node == NULL) { continue; } if(temp->colour == 0) { StacktNode* right = new StacktNode(temp->node->right,NULL); stack->push(right); temp->colour=1; stack->push(temp); StacktNode* left = new StacktNode(temp->node->left,NULL); stack->push(left); }else if(temp->colour==1) { cout<<" "<<temp->node->data; } } return; } int LintkedIntTree::heightRec(BinaryTreeIntNode* node) { if(node == NULL) { return 0; } int h1 = heightRec(node->left); int h2 = heightRec(node->right); h1++; h2++; return h1>h2?h1:h2; } int LintkedIntTree::height(bool isRecursive) { if(isRecursive) { return heightRec(root); } else { StacktNode* node = new StacktNode(root,NULL); StackInt* stack = new StackInt(node,1); return heightNonRec(stack); } } int LintkedIntTree::heightNonRec(StackInt* stack) { int maxh = 1; int h = 1; if(stack == NULL) { return -1; } while(!stack->isEmpty()) { maxh = maxh>h?maxh:h; StacktNode* temp=stack->pop(); h--; if(temp->node==NULL) { continue; } if(temp->colour == 0)//no child has been visited. { temp->colour=1; h++; stack->push(temp); if(temp->node->left!= NULL) { h++; StacktNode* left = new StacktNode(temp->node->left,NULL); stack->push(left); } }else if(temp->colour==1) { temp->colour=2; h++; stack->push(temp); if(temp->node->left!= NULL) { h++; StacktNode* right = new StacktNode(temp->node->right,NULL); stack->push(right); } }else { continue; } cout<<" h ="<<h<<endl; } return maxh; }