Heap vs Binary Tree

Harsh Dawar -

Do not miss this exclusive book on Binary Tree Problems. Get it now for free.

Today we are going to compare two non linear data structures binary trees and heaps since both are non liner there tend to be confusion regarding both of these usually we will try to remove these confusion.

See the summary table of differences at the end of this article

Introduction

Binary tree

A binary tree is a non-Linear data structure in which each node can have either 0, 1 or 2 child nodes each. Each node consists of

  • Data portion
  • Pointer to left child
  • Pointer to right child

Depending upon how these nodes are arranged there are many kinds of Binary trees

  • Full Binary Tree
  • Complete Binary tree
  • Perfect Binary tree
  • Balanced Binary tree
  • Skewed Binary tree
class BinaryTreeNode{
public:
    int data;
    BinaryTreeNode* left_child;
    BinaryTreeNode* right_child;
};

Heap

Heap is a special kind of tree based data structure in which it is a complete binary tree and it satisfies the heap property

  • a node is always greater than its child nodes the key of root node is largest among all nodes this is the max heap property
  • a node is always smaller than is child nodes and the key of the root node is smallest among all the nodes this is called the min heap property

Rather than creting a class or struct a heap is usually represented using a linear data structure with random access such as vector or array where if the parent element lies at ith then left child lies at 2i+1th index and right child lies at 2i+2th index;

Whenever a operation is performed on heap it may loose its fundamental heap property to solve this problem we use a special function called the heapify function which restores the heap property.

void swap(int *a, int *b){
    int temp = *a;
    *a = *b;
    *b = temp;
}

void heapify(vector<int> &heap, int i){
    int s = heap.size();
    int largest = i;
    int l = 2*i + 1;
    int r = 2*i + 2;
    if(l < s && heap[l] > heap[largest])
        largest = l;
    if(r < s && heap[s] > heap[largest])
        largest = s;
    
    if(largest != i){
        swap(&heap[i], &heap[largest]);
        heapify(heap, largest);
    }
}

Similarly we can change this to work for min heaps also.

Difference in operations

Similar to any other data structure ob both heap and binary tree we can perform traversal, insertion and deletion

Insertion

Since there is no ordering in binary treee we can insert a new node below any node with no more than 1 child already present

In binary tree can insert anywhere we want or trverse the tree levelwise and use a function to insert the node at first favourable position we see

BinaryTreeNode* InsertNode(BinaryTreeNode* root, int data){
    if(root == nullptr){
        auto* new_node = new BinaryTreeNode(data);
        return new_node;
    }
    else {
        queue<BinaryTreeNode *> q;
        q.push(root);

        while (!q.empty()) {
            BinaryTreeNode *temp = q.front();
            q.pop();

            if (temp->left_child != nullptr)
                q.push(temp->left_child);
            else {
                temp->left_child = new BinaryTreeNode(data);
                return root;
            }

            if (temp->right_child != nullptr)
                q.push(temp->right_child);
            else {
                temp->right_child = new BinaryTreeNode(data);
                return root;
            }
        }
    }
}

This function traverses the tree level by level and the fisr instanace that it gets a node with 1 or less children it inserts the new node below that node.

But, when we insert a new node into heap we need to maintain the heap property. So during insertion we just insert a new value into the heap vector or array and call the heapify function to maintain the heap property

void InsertHeap(vector<int> &heap, int data){
    if(heap.empty()){
        heap.push_back(data);
    }
    else{
        heap.push_back(data);
        for(int i = heap.size()/2 - 1; i >= 0; i--){
            heapify(heap, i);
        }
    }
}

Traversal

Since heap are stored in the form of linear data structure they can be traversed as is on the other hand on binary tree we can perform inorder, pre-order, post-order traversal. Lets learn about these traversals.

  1. Inorder Traversal - first the left child is printed followed by parent and then right child
  2. Post-order Traversal - first the left and right child are printed followed by the parent node.
  3. Pre-order Traversal - First the parent node is printed followed by left and right childern of that node.

Inorder Traversal

  • Traverse the left subtree
  • Visit the root node
  • Traverse the right sub tree

Postorder Traversal

  • Traverse the left subtree
  • Traverse the right sub tree
  • Visit the node

Preorder Traversal

  • Visit the node
  • Traverse the left subtree
  • Traverse the right sub tree
void Inorder(BinaryTreeNode* root){
    if(root == nullptr){
        return;
    }
    Inorder(root->left_child);
    cout << root->data;
    Inorder(root->right_child);
}

void Postorder(BinaryTreeNode* root){
    if(root == nullptr){
        return;
    }
    Postorder(root->left_child);
    Postorder(root->right_child);
    cout << root->data << " ";
}

void Preorder(BinaryTreeNode* root){
    if(root == nullptr){
        return;
    }
    cout << root->data;
    Preorder(root->left_child);
    Preorder(root->right_child);
}

Traversal of a heap

  • Traverse and print the vector as is
void printHeap(const vector<int>& heap){
    for(int i : heap){
        cout << i << " ";
    }
    cout << endl;
}

Deletion of a node

When we want to delete a node in bianry tree we need to take note that children of that node stay attached to the tree

  • First we find the deepest rightmost node in the said tree and the node which we want to delete.
  • swap the node to be deleted and rightmost node
  • delete the node to be deleted now at the deepest rightmost position
void deleteLast(BinaryTreeNode* root, BinaryTreeNode* del){
    queue<BinaryTreeNode*> q;
    q.push(root);
    BinaryTreeNode* temp = nullptr;
    // traversing the tree and finding the node to be deleted
    while(!q.empty()){
        temp = q.front();
        q.pop();
        if (temp == del){
            temp == nullptr;
            delete(del);
            return;
        }
        
        if (temp->right_child){
            if(temp->right_child == del){
                temp->right_child == nullptr;
                delete(del);
                return;
            }
            else{
                q.push(temp->right_child);
            }
        }
        
        if(temp->left_child){
            if(temp->left_child == del){
                temp->left_child == nullptr;
                delete(del);
                return;
            }
            else{
                q.push(temp->left_child);
            }
        }
    }
}

BinaryTreeNode* deleteLast(BinaryTreeNode* root, int x){
    // Implementation for edge cases
    if(root == nullptr){
        return nullptr;
    }
    if(root->left_child == nullptr && root->right_child == nullptr){
        if(root->data == x){
            return nullptr;
        }
        else{
            return root;
        }
    }
    queue<BinaryTreeNode*> q;
    q.push(root);
    
    BinaryTreeNode* temp = nullptr;
    BinaryTreeNode* Node = nullptr;
    // traversing the tree and storing the required node in Node
    while(!q.empty()){
        temp = q.front();
        q.pop();
        
        if(temp->data == x){
            Node = temp;
        }
        
        if(temp->left_child){
            q.push(temp->left_child);
        }
        
        if(temp->right_child){
            q.push(temp->right_child);
        }
    }
    // now the last node is stored in temp and required node in Node
    if(Node != nullptr){
        int data_last = temp->data;
        deleteLast(root, temp);
        Node->data = data_last;
    }
    return root;
}

However The deletion from heaps is whole lot simpler. If the node to be deleted is leaf node we can simply delete the node. Else we can swap the node to be deleted with the last node and call the heapify function.

void deleteNode(vector<int> &heap, int x){
    unsigned int s = heap.size();
    unsigned int i;
    for (i = 0 ; i < s ; i++){
        if(x == heap[i])
            break;
    }
    swap(&heap[i], &heap[s - 1]);
    heap.pop_back();
    for(int j = s/2 -1; j >= 0 ; j-- ){
        heapify(heap, j);
    }

}

Applications

Both Heaps and Binary Trees have multitude of uses all aroud

Some major applications of Heaps are-

  • Heaps are the practical implementation of priority queues as they enable us to not only push to the end of queues but lso to the middle of start of queue based on what the heapify function sorts the heap
  • Heaps are essential in the implementation of Dijkstra's algorithm
  • And obviously heaps are the basis of implementation of heap sort

On the other hand binary trees are probably the most important data structurethey form the bass of many other data structures even heaps the major applications of biary trees are the following

  • Binary trees are used to maintain the routing tables in routers
  • Binary trees are critical for binary search trees which are used when there is data constantly entering and leaving.
  • Used in Binary Space Partition an important concept in 3D games which determines which artifacts need to be rendered
  • Huffman Coding is based on Binary trees which is itself a critical part of compressio algorithms used by .jpeg and .mp3 formats
Title Binary Tree Heap
Structure Binary Tree like any other Tree
based data structure is represented
using class having a data portion and
pointers to its children.		 Heap Data stucture however is
represented using a linear data
stucture like an array or a
vector where if the parent lies at
ith postion then the children lie at
2i + 1th position and 2i + 2th
position
Insertion Since there is no ordering
in a binary tree hence a
new node can be inserted below
the first node from left in the
bottom most level that does not
have 2 children		 Since there is an ordering be
it min or max heap we just append
the new node to vector and call
the heapify function to restore
the heap order.
Traversal we can traverse the binry tree
in inorder, preorder and
postorder format		 Heap can be only traversed linearly
Deletion We swap the node to be deleted by
the bottom rightmost node and then
delete the bottom rightmost node		 We simply locate and delete the
required node and call the heapify
function to restore the heap order
Application Maintain routing tables i routers,
Heaps, Huffman coding and Binary
search trees		 heaps are the practical implementation
of priority queues and are important
for implementation of Djikstras
Algorithm and Heap sort.

With this article at OpenGenus, you must have the complete idea of Heap and Binary Tree.

Sign up for FREE 3 months of Amazon Music. YOU MUST NOT MISS.