DSA: Binary Heap Tree

    A Heap binary tree is a balanced binary data structure where the parent node either be larger or smaller than its child node, depends upon the type of heap binary structure. The binary heap was first introduced in 1964 by J.W.S Williams, as a data structure for heap sort. We commonly use a heap binary data structure for the implementation of priority queues.

    Binary Heap Property

    Binary Heap has two properties:

    • Shape Property
    • Heap Property.

    Shape Property: The heap binary tree should be a complete balanced binary tree, where each parent node has 2 child nodes except the last level. The insertion of the new element takes place at the bottom of the heap tree from left to right. Heap Property: Each node has a key-value that could be either greater than or less than the parent node, depends upon the type of binary heap.

    Types of Heap Tree

    There are two types of heap tree:

    • Max heap
    • Min Heap

    Max heap

    In max heap the parent node key value is either greater or equal to its child node. Example:

                                        100
                                       /   \
                                      /     \
                                    20       11
                                   /   \    /  \
                                 18    10  4    6
                                /  \
                               9    3

    In the above example, we have designed a max heap binary tree, where each parent node is greater than its children.

    Min heap

    In min-heap, the parent node key value is either less than or equal to its child node key value.

    Example:

                                       1
                                     /   \
                                    /     \
                                  20       11
                                 /   \    /  \
                               21    22 23    24
                              /  \
                            35    36

    Binary Heap Operation

    There are two basic operations we can perform in Binary heap tree.

    • Insertion
    • Deletion

    Because with insertion and deletion of the element from a heap tree can affect the properties of a heap tree so let’s considers these operations first.

    Insert

    The insertion takes place at the bottom level of the heap tree from left to right, it maintains the tree balanced and complete. If we insert a new element in the heap tree and the heap property remain satisfied, we leave the tree there itself, if the insertion of new element violates the heap property then we need to perform the up-heap operation on the tree, which swaps the newly added element with its parent element.

    Example: Max heap tree:

                                          100
                                         /   \
                                        /     \
                                     20       11
                                    /   \    /  \
                                  18    10  4   6

    Insert 200 The insertion takes place at the bottom left.

                                     100
                                    /   \
                                   /     \
                                 20       11
                                /   \    /  \
                              18    10  4    6
                              / 
                            200

    It violates the max heap property the child element is greater than its parent (200 > 18), now we will perform the up-head operation to maintain the heap property. Swap new element with its parent element.

                                        100
                                       /   \
                                      /     \
                                    20       11
                                   /   \    /  \
                                200    10  4    6
                                / 
                              18

    Yet the child is greater than its parent, again perform the up-head operation swap 200 with 20

                                      100
                                     /   \
                                    /     \
                                 200       11
                                /   \     /  \
                               20    10  4    6
                              / 
                             18

    The root node is smaller than its child node so, aging use the up-head operation, and swap 200 with 100

                                       200
                                      /   \
                                     /     \
                                  100       11
                                 /   \    /  \
                                20    10  4    6
                               / 
                             18

    Insertion complete.

    Deletion

    The deletion operation is a little complex for a heap tree. The deletion of leaf element is easy, but deleting a root node can disturb the heap properties. So, to delete the parent or root node we use the down heap operation, which restores the heap property if we want to delete the root node. Steps to delete an element from a heap tree.

    • Replace the element with the last element, and delete the last element.
    • Now compare the new element with its child node, it the heap property satisfy leave the tree and stop the insertion operation.
    • If not compare the swapped parent element with its child element and swap them until the tree property get satisfies.

    Example: Max heap tree.

                                 200
                                /   \
                               /     \
                            100       11
                           /   \    
                         20    10

    Delete 200: Swap the last element (10) with the element supposed to delete (200), and delete the last element

                                   10
                                  /   \
                                 /     \
                              100       11
                             /   \     
                           20    200

    Deleting last element.

                                 10
                                /   \
                               /     \
                            100       11
                           /   \   
                         20

    The node element is smaller than its child element it violates the heap property do to restore the heap property we perform the down heap operation. The down heap operation swaps the parent element with its child if they violate the heap property. Swap 10 with 100

                                     100
                                    /   \
                                   /     \
                                 10       11
                               /   \   
                              20

    Yet 10 is smaller than 20 which violate the heap tree property, so again imply the down heap operation and swap 10 with 20.

                               100
                              /   \
                             /     \
                           20       11
                         /   \   
                        10

    Done.

    Implementation of a heap tree

    Here we have implemented a min heap tree with the help of array.

    class Binary_Heap:
    
        def __init__(self):
            self.heaplist=[0]
            self.current_Size=0
    
        def up_heap(self,i):
            while i//2>0:
                if self.heaplist[i] < self.heaplist[i//2]:
                    self.heaplist[i//2],self.heaplist[i]=self.heaplist[i],self.heaplist[i//2]
                i = i//2
         
        def insert(self,data):
            self.heaplist.append(data)
            self.current_Size+=1
            self.up_heap(self.current_Size)
    
        def down_heap(self,i):
            while(i*2)<=self.current_Size:
                mc= self.minchild(i)
                if self.heaplist[i]>self.heaplist[mc]:
                    heaplist[i],heaplist[mc]=heaplist[mc],heaplist[i]
                i=mc
        
        def minchild(self,i):
            if i*2+1>self.current_Size:
                return i*2
            else:
                if self.heaplist[i*2]<self.heaplist[i*2+1]:
                    return i*2
                else:
                    return i*2+1
        def del_min(self):
            r = self.heaplist[1]
            self.heaplist[1]=self.heaplist[self.current_Size]
            self.current_Size-=1
            self.heaplist.pop()
            self.down_heap(1)
            return r
                
       def show(self):
           return self.heaplist[1:]
    
    heap_tree = Binary_Heap()
    heap_tree.insert(100)
    heap_tree.insert(200)
    heap_tree.insert(300)
    heap_tree.insert(70)
    heap_tree.insert(20)
    print(heap_tree.show())

    Output:

    [20, 100, 300, 700, 200]

    Equivalent Output:

    Insert(100)
                                       100
                                                                   
    Min heap property satisfy
    
    Insert 200
                                      100
                                     / 
                                    /    
                                  10  
    Min heap property satisfy
    Insert 300
    
                               100
                              /   \
                             /     \
                          200       300
    Min heap property satisfy
    
    Insert 700:
    
                               100
                              /   \
                             /     \
                          200       300
                           /
                        700
    Min heap property satisfy
    
    Insert 20
                         100
                        /   \
                       /     \
                     200     300
                    /   \
                  700   20
    
    Min Heap property violate apply up_heap operation
    
                                      20
                                    /   \
                                   /     \
                                100       300
                              /    \
                           700     200
    
    Represent the above tree in array
    
    [20,100,300,700,200]

    People are also reading: