Binary Heap in Python

A binary heap is a Binary Tree with the following properties:

• It is a complete tree, i.e., all levels of the tree are filled except possibly the last level and the leaf nodes are as left as possible. This property of Binary Heap makes them more suitable to be stored in ann array.
• A Binary Heap is either Min Heap or Max Heap. In a Min Binary Heap, the key at root must be minimum among all keys present in Binary Heap. The same property must be recursively true for all nodes in Binary Heap Tree. Max Binary Heap is similar to MinHeap wherein all root nodes hold the max value among their children.

A binary heap can be quite useful to find the maximum or minimum number among a set of given numbers in O(logN) time. The binary heap also ensures that insertion in the heap takes O(logN) time as well. This significantly improves the time efficiency of implementing such operations.

A binary heap is the heart of some crucial problems which would be later discussed. The knowledge of binary heap is necessary for solving the following problems:

• Prim’s Algorithm
• Heap Sort
• Priority Queue

Implementation of Binary Heap built using List

A binary heap is a form of a binary tree. Hence, similar to the Binary tree, we can implement a binary heap using Python’s list data structure. The root node of the binary heap is stored at the first index of the list data structure. Subsequently, we enter all the data elements in an ordered manner.

If a parent node of a subtree in the binary heap is placed at the index i of the list, then the left child of the parent is stored at the index 2i and the right child is stored at the position 2i+1. The same procedure is followed for every node in the binary heap until all the elements have been inserted.

Operations on Binary Heap built using List

Creation of Binary Heap

To create a binary heap in python, we first need to declare a “BHeap” class. Within that heap class, we will initialize the __init__ function.

Implementation of Creation of Binary Heap

The __init__ function takes the size of the Binary Heap as its argument. We need to declare three variables within our “BHeap” class:

• customList to initialize the list in which data elements will be stored.
• heapSize stores the number of elements filled in the binary heap, which is initialized to zero.
• maxSize which is 1 more than Size because the first index of the list is left empty.

#Creation of Binary Heap using List
class BHeap:
    def __init__(self, size):
        self.customList = (size+1) * [None]
        self.heapSize = 0
        self.maxSize = size + 1

newBinaryHeap = BHeap(5)

Time and Space Complexity

The time complexity for the creation of the binary heap is O(1) because no additional time is required to initialize data items. The space complexity is O(N) because we initialize a list of the same size as that of the binary heap.

Peek Function on Binary Heap

The peek function returns the topmost element in a data structure. In the case of a binary heap, the peek function is used to return the root node of the heap.

Implementation of Peek Function

To implement peek in a binary heap, we create the custom function peekofBHeap which takes the reference to the binary heap as its argument. We know that the root node of a binary tree is stored at the first index of the list. Thus, we simply return the first element of the list by indexing.

#Function to find peek element in a Binary Heap
def peekofBHeap(rootNode):
    if not rootNode:
        return
    else:
        return rootNode.customList[1]

Time and Space Complexity

The time complexity for the creation of the peek function for the binary heap is O(1) because it takes a constant time to return an element through the function. The space complexity is O(1) as well because no additional memory is required.

Size Function on Binary Heap

The size function returns the number of elements filled in the data structure. In the case of a binary heap, we maintain a data variable to dynamically store the number of filled spaces in the list.

Implementation of Size Function

To implement the size function in a binary heap, we create the a function sizeofBHeap which takes the reference to the binary heap as its argument. We simply return the heapSize data variable to indicate how many elements have been entered at the time of the function call.

#Function to find size of the Binary Heap
def sizeofBHeap(rootNode):
    if not rootNode:
        return
    else:
        return rootNode.heapSize

newBinaryHeap = BHeap(5)
print(sizeofBHeap(newBinaryHeap))

#Output
0

Time and Space Complexity

The time complexity for the creation of the size function for the binary heap is O(1) because it takes a constant time to return an element through the function. The space complexity is O(1) as well because no additional memory is required.

Level Order Traversal in Binary Heap

Binary Heap can be traversed in a level order manner. The Level Order traversal is a breadth-first traversal where nodes are visited level-by-level. Then, they are traversed in a left-to-right manner.

Example:

Level Order Traversal – N1 -> N2 -> N3 -> N4 -> N5 -> N6 -> N7 -> N8 -> N9

Implementation of Level Order Traversal

While using a list data structure to implement binary heap, the elements are stored in an ordered manner in the list data structure. They are ordered as per their level in the binary heap. Further, they are sorted from left to right at a particular level.

Thus, we define a function levelOrderTraversal which takes the root node of the binary heap as its parameter. Within this function, we iterate the list using a for loop statement and print each element in the same manner as they are stored in the list.

#Function to perform Level Order Traversal in Binary Heap
def levelOrderTraversal(rootNode):
    if not rootNode:
        return
    else:
        for i in range(1, rootNode.heapSize+1):
            print(rootNode.customList[i])

Time and Space Complexity

The time complexity for level order traversal of the binary heap is O(N) because we iterate over the entire list, printing each visited element. The space complexity is O(1) as well because no additional memory is required.

Insertion of a Node in Binary Heap

While inserting a node in a binary tree, we must keep in mind whether the binary heap is a min-heap or a max heap. Any newly inserted node must not disturb the basic property of the binary heap.

Thus, we keep swapping the newly added node with its adjacent nodes based on their values. This adjustment is continued until the newly added node reaches its correct position in the binary heap.

Implementation of Insertion of a Node in Binary Heap

The implementation of insertion in a binary heap requires that the fundamental property of the heap is not altered. Thus, first, we will create a method heapifyTreeInsert to heapify the tree, i.e., restore it to its fundamental structure after insertion.

The function heapifyTreeInsert takes three arguments – the root node of the binary heap, the index of the node to be adjusted, and the type of binary heap. The function recursively swaps the position of the newly added node with its adjacent nodes based on the values of the nodes. This process is continued until the inserted node is placed at its correct position in the binary heap.

#Function to heapify the Binary Heap while Insertion
def heapifyTreeInsert(root_node, index, heapType):
    parentIndex = int(index/2)
    if index <= 1:
        return
    if heapType == "Min":
        if root_node.customList[index] < root_node.customList[parentIndex]:
            temp = root_node.customList[index]
            root_node.customList[index] = root_node.customList[parentIndex]
            root_node.customList[parentIndex] = temp
        heapifyTreeInsert(root_node, parentIndex, heapType)
    elif heapType == "Max":
        if root_node.customList[index] > root_node.customList[parentIndex]:
            temp = root_node.customList[index]
            root_node.customList[index] = root_node.customList[parentIndex]
            root_node.customList[parentIndex] = temp
        heapifyTreeInsert(root_node, parentIndex, heapType)

Now we create the insertNode method to insert nodes into the binary heap. The function takes three arguments – the root node of the binary heap, the value of the node to be inserted, and the type of the binary heap.

• The function checks whether or not the binary heap has reached its max occupancy. If that happens, the message “Binary Heap is fully occupied” is returned.
• The next step is to insert the value of the node in the next vacant space in the list.
• Then, a function call to heapifyTreeInsert is made to adjust the newly inserted to its rightful position in the binary heap.

#Function to Insert a Node in Binary Heap
def inserNode(root_node, nodeValue, heapType):
    if root_node.heapSize + 1 == root_node.maxSize:
        return "The Binary Heap is fully occupied."
    root_node.customList[root_node.heapSize + 1] = nodeValue
    root_node.heapSize += 1
    heapifyTreeInsert(root_node, root_node.heapSize, heapType)
    return "The node has been successfully inserted."

#Initializing the Binary Heap
newHeap = BHeap(10)
inserNode(newHeap, 70, "Max")
inserNode(newHeap, 40, "Max")
inserNode(newHeap, 30, "Max")
inserNode(newHeap, 60, "Max")
inserNode(newHeap, 80, "Max")
inserNode(newHeap, 20, "Max")
inserNode(newHeap, 5, "Max")
inserNode(newHeap, 50, "Max")
inserNode(newHeap, 10, "Max")
levelOrderTraversal(newHeap)

Output

Time and Space Complexity

The recursive function heapifyTreeInsert swaps the value of the node with its adjacent value repeatedly. The correct position is found by dividing the tree subsequently at each level. In this way, the number of function calls takes the form of logN. Hence, the time complexity for search is O(logN).

The space complexity is O(logN) as well because every time the function is called, it allocates space in the stack in memory to determine the next function call.

Extraction of a Node from a Binary Heap

The term “Extraction” means the deletion of the root node from a binary heap. While extracting a node in a binary tree, we must keep in mind whether the binary heap is a min-heap or a max heap. Whenever a node is extracted from the heap, it may disturb its fundamental property.

Thus, we first swap the node to be deleted by the last node of the heap. Then, we delete that node and adjust the replaced node using the heapify algorithm for the deletion method.

Implementation of Extraction of a Node from Binary Heap

The implementation of extraction from a binary heap requires that the fundamental property of the heap is not altered. Thus, first, we will create a method heapifyTreeExtract to heapify the tree, i.e., restore it to its fundamental structure after extraction.

The function heapifyTreeExtract takes three arguments – the root node of the binary heap, the index of the node to be adjusted, and the type of binary heap. The function recursively swaps the position of the root node, i.e., the swapped node, with its adjacent nodes based on the values of the nodes. This process is continued until the swapped node is placed at its correct position in the binary heap.

#Function to heapify the Binary Heap while Extraction
def heapifyTreeExtract(root_node, index, heapType):
    leftIndex = index * 2
    rightIndex = index * 2 + 1
    swapChild = 0

    if root_node.heapSize < leftIndex:
        return
    elif root_node.heapSize == leftIndex:
        if heapType == "Min":
            if root_node.customList[index] > root_node.customList[leftIndex]:
                temp = root_node.customList[index]
                root_node.customList[index] = root_node.customList[leftIndex]
                root_node.customList[leftIndex] = temp
            return
        else:
            if root_node.customList[index] < root_node.customList[leftIndex]:
                temp = root_node.customList[index]
                root_node.customList[index] = root_node.customList[leftIndex]
                root_node.customList[leftIndex] = temp
            return

    else:
        if heapType == "Min":
            if root_node.customList[leftIndex] < root_node.customList[rightIndex]:
                swapChild = leftIndex
            else:
                swapChild = rightIndex
            if root_node.customList[index] > root_node.customList[swapChild]:
                temp = root_node.customList[index]
                root_node.customList[index] = root_node.customList[swapChild]
                root_node.customList[swapChild] = temp
        else:
            if root_node.customList[leftIndex] > root_node.customList[rightIndex]:
                swapChild = leftIndex
            else:
                swapChild = rightIndex
            if root_node.customList[index] < root_node.customList[swapChild]:
                temp = root_node.customList[index]
                root_node.customList[index] = root_node.customList[swapChild]
                root_node.customList[swapChild] = temp
    heapifyTreeExtract(root_node, swapChild, heapType)

Now we create the extractNode method to extract nodes from the binary heap. The function takes two arguments – the root node of the binary heap and the type of the binary heap.

• The function checks whether or not the binary heap is empty. If that happens, the message “Binary Heap is empty” is returned.
• The next step is to swap the root node of the heap with the last node.
• Further, the last node is deleted from the list.
• Then, a function call to heapifyTreeExtract is made to adjust the newly inserted to its rightful position in the binary heap.

#Function to Extract a Node from Binary Heap
def extractNode(root_node, heapType):
    if root_node.heapSize == 0:
        return "The Binary Heap is empty."
    else:
        extractedNode = root_node.customList[1]
        root_node.customList[1] = root_node.customList[root_node.heapSize]
        root_node.customList[root_node.heapSize] = None
        root_node.heapSize -= 1
        heapifyTreeExtract(root_node, 1, heapType)
        return extractedNode

#Initializing the Binary Heap
newHeap = BHeap(10)
inserNode(newHeap, 70, "Max")
inserNode(newHeap, 40, "Max")
inserNode(newHeap, 30, "Max")
inserNode(newHeap, 60, "Max")
inserNode(newHeap, 80, "Max")
inserNode(newHeap, 20, "Max")
inserNode(newHeap, 5, "Max")
inserNode(newHeap, 50, "Max")
inserNode(newHeap, 10, "Max")

extractNode(newHeap, "Max")
levelOrderTraversal(newHeap)

Output

Time and Space Complexity

The recursive function heapifyTreeExtract swaps the value of the root node with its adjacent value repeatedly. The correct position is found by dividing the tree subsequently at each level. In this way, the number of function calls takes the form of logN. Hence, the time complexity for search is O(logN).

The space complexity is O(logN) as well because every time the function is called, it allocates space in the stack in memory to determine the next function call.

Clearing of Entire Binary Heap

To delete an entire binary heap, we simply set the basic list to None. This way we free up the allocated memory space.

#Function to Delete Entire Binary Heap
def deleteEntireBP(root_node):
    root_node.customList = None
    print ("The binary heap has been successfully deleted.")

#Initializing the Binary Heap
newHeap = BHeap(10)
inserNode(newHeap, 70, "Max")
inserNode(newHeap, 40, "Max")
inserNode(newHeap, 30, "Max")
inserNode(newHeap, 60, "Max")
inserNode(newHeap, 80, "Max")
inserNode(newHeap, 20, "Max")
inserNode(newHeap, 5, "Max")
inserNode(newHeap, 50, "Max")
inserNode(newHeap, 10, "Max"))

deleteEntireBP(newHeap)

#Output
The binary heap has been successfully deleted.

Time and Space Complexity

The time complexity for deletion of the entire binary heap is O(1) since it takes constant time for setting the list to None. The space complexity is O(1) as well since no additional memory is required for deletion.

	Time Complexity	Space Complexity
Creation of Binary Heap	O(1)	O(N)
Peek Function	O(1)	O(1)
Size Function	O(1)	O(1)
Level Order Traversal	O(N)	O(1)
Insertion	O(logN)	O(logN)
Extraction	O(logN)	O(logN)
Clearing of Binary Heap	O(1)	O(1)