Heap vs Binary Tree

Open-Source Internship opportunity by OpenGenus for programmers. Apply now.

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 i^th then left child lies at 2i+1^th index and right child lies at 2i+2^th 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.

Inorder Traversal - first the left child is printed followed by parent and then right child
Post-order Traversal - first the left and right child are printed followed by the parent node.
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 i^th postion then the children lie at 2i + 1^th position and 2i + 2^th 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.