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: