DSA: Binary Heap Tree

By | January 5, 2020
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.

Vamware

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]

You may be also interested in:

Leave a Reply

Your email address will not be published. Required fields are marked *