What is Binary Heap?

Fatima JannetFatima Jannet
7 min read

Table of contents

If you're new to this blog, it would be great if you could check out the posts on Binary Trees, BSTs, and AVLs.

Binary Tree , BST, AVL

Let's get started!

A Binary Heap is a Binary Tree with following properties:

  • A binary heap can be a Min heap or Max heap. In a Min heap, the root key is the smallest among all keys in the heap. This property must hold true for all nodes in the tree.

  • It's a complete tree (all levels are fully filled except possibly the last, which has keys as left as possible). This makes Binary Heaps suitable for storage in an array.

Due to the second property, it's ideal for implementation in an array or Python list, because we usually want to fill the maximum number of cells in a fixed-size array.

Why we need Binary Heap?

Let's look at a question: Find the minimum or the maximum number among a set of numbers in logN time. Also, make sure that insertion additional numbers does not take more than O(logN) time.

Possible solutions:

  • Store the numbers in sorted Array

    | 10 | 20 | 30 | 40 | 50 | |

    Find minimum: O(1)

    Problem: When inserting an element (5) at the beginning of this list, we have to shift all elements one step to the right. In the worst case, this takes O(n) time complexity. So, this isn't a solution to our problem.

  • Store the numbers in Linked List in sorted manner

    Problem : When we insert an element into linked list, we traverse through the linked list to find the appropriate place for the node. In the worst case, this process takes O(n) time complexity

We want a solution which takes O(logN) time complexity. So the only solution is to use Binary Heap. We already know it's a binary tree with additional property. With the use of BP, we can find the maximum/minimum number from a set of number. BP will not fail like array or linked list. BP will complete the task with the time complexity of O(logN)

Practical use :

  1. Prim's Algorithm

  2. Heap Sort

  3. Priority Queue

BP types :

  1. Min heap: the value of each node is less than or equal to the value of both its children

  2. Max heap: The value of each node is more than or equal to the value of both its children.

Common operations

The common operations are - Creation, Peek top of BP, traversal, size of BP, insertion, extract min/max, deletion.

Implementation Options : Array implementation, Reference/pointer

These implementations are quite similar. We will use array based implementation because array ins the best fit for binary heap.

Based on this two formula, we insert values to the array/python list. The root node's index is 1. (left child = cell [2x]) So, 1 is multiplied with 2, so the index of left child will be two. Then, we are multiplying 2 with 1 and plus 1 which is 3, so we are inserting 20 there. [ x = index of parent ]

  1. Creation of BP

    • Initialize fixed size list

    • set size of BP to 0

    class Heap: 
        def __init__(self, size): 
            self.customList = (size+1) * [None] 
            self.heapSize = 0
            self.maxSize = size + 1 
    newBinaryHeap = Heap(5)

The line (size+1) * [None] is used to create a list (array) of a fixed size, filled with None values initially. By creating an array of size size + 1, you leave index 0 empty (None) and use indices from 1 to size.

Time complexity: O(1), Space complexity: O(N) [initializing fixed sized list]

  1. Peek of BP

    • Return list [1]

In our case, root of heap is 5. So, we are returning 5 (root is always located in the index of 1)

    def peekOfHeap(rootNode): 
        if not rootNode: 
            return 
        return rootNode.customList[1] 
    newBinaryHeap = Heap(5)

Time complexity: O(1), Space complexity: O(1)

  1. Size of binary heap

    • return number of filled cells

Basically, it means how many elements are there in the heap

    def sizeOfHeap(rootNode): 
        if not rootNode: 
            return 
        return rootNode.heapSize 
    newBinaryHeap = Heap(5) 
    print(sizeOfHeap(newBinaryHeap))

Time complexity: O(1), Space complexity: O(1)

  1. Traversal of BP

    • level order traversal

      (I have explained everything of level order traversal in Binary Tree blog, hence I'm not going to discuss about it here)

        def levelOrderTraversal(rootNode): 
      if not rootNode: 
          return None 
      else: 
          for i in range(1, rootNode.heapSize+1): 
              print(rootNode.customList[i])

      Time complexity: O(n), Space complexity: O(1)

Insert a node in Binary Heap

According to the properties of binary heap, it should be a complete tree. But in the last level, we can have as many nodes left as possible. There is a unused cell, and in the list there's an empty index is present. We can insert a number over there.

After we insert 1 over here, it will look like this -

But it violates the rule of BP that is the root node must be smaller than every node in the heap. Now, we need to make adjustment. We will keep swapping the child node with the parent node until the property becomes maintained.

For creating method for insertion, we will create heapify tree method (this method is needed for both insertion and deletion)

def heapifyTreeInsert(rootNode, index, heapType): 
    parentIndex = int(index/2) 
    if index <= 1: 
        return 
    if heapify == "Min": 
        if rootNode.customList[index] < rootNode.customList[parentIndex]:
            temp = rootNode.customList[index] 
            rootNode.customList[index] = rootNode.customList[parentIndex]
            rootNode.customList[parentIndex] = temp
        heapifyTreeInsert(rootNode, parentNode, heapType) #O(logN)
    elif heapify == "Max": 
        if rootNode.customList[index] > rootNode.customList[parentIndex]:
            temp = rootNode.customList[index] 
            rootNode.customList[index] = rootNode.customList[parentIndex]
            rootNode.customList[parentIndex] = temp
        heapifyTreeInsert(rootNode, parentNode, heapType) #O(logN)
# Time complexity: O(logN), Space complexity: O(logN)

def insertNode(rootNode, nodeValue, heapType): 
    if rootNode.heapSize + 1 == rootNode.maxSize : 
        return "The binary heap is full" 
    rootNode.customList[rootNode.heapSize + 1] = nodeValue 
    rootNode.heapSize += 1 
    heapifyTreeInsert[rootNode, rootNode.heapSize, heapType) #O(logN)
    return "The value has been successfully inserted" 
newHeap = Heap(5) 
insertNode(newHeap, 4, "Max") 
insertNode(newHeap, 5, "Max") 
insertNode(newHeap, 3, "Max") 
insertNode(newHeap, 1, "Max") 
levelOrderTraversal(newHeap)
# Time complexity: O(logN), Space complexity: O(logN)

Extract a node from Binary Heap

The only one element that can be extracted from heap is always the root. Other node extraction are not allowed because it hampers the property of heap. In that case, we need to do some adjustments.

Steps:

  1. Find the last element of the heap (which is located at the last level)

  2. Replace the last element with the root node

  3. Adjustment : Promote one of the children of the root node, and replace their place (select the minimum child) Keep repeating the process.

    Note: In case if Min BP, the left node is always bigger than the rootNode.

def heapifyTreeExtract(rootNode, index, heapType): 
    leftIndex = index * 2 
    rightIndex = index * 2 + 1 
    swapIndex = 0 

    if rootNode.heapSize < leftIndex: 
        return 

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

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

def extractNode(rootNode, heapType): 
    if rootNode.heapSize == 0: #O(1)
        return 
    else: 
        extractedNode = rootNode.customList[1]  #O(1)
        rootNode.customList[1] = rootNode.customList[rootNode.heapSize] #O(1)
        rootNode.customList[rootNode.heapSize] = None  #O(1)
        rootNode.heapSize -= 1 #O(1)
        heapifyTreeExtract(rootNode, 1, heapType)  #O(logN)
        return extractedNode  #O(1)

newHeap = Heap(5) 
insertNode(newHeap, 4, "Max") 
insertNode(newHeap, 5, "Max") 
insertNode(newHeap, 3, "Max") 
insertNode(newHeap, 1, "Max") 
print(extractNode(newHeap, "Max"))
levelOrderTraversal(newHeap)

  • In case of minimum heap, we have to find the smallest child, then swap it with the parent

  • In case of maximum heap, we have to find the greatest child, then swap it with the parent

Time complexity: O(logN), Space complexity: O(logN)

Inside heapify method, we are calling method recursively and that's why it takes O(logN) space complexity

Delete entire Binary Heap

def deleteEntireBP(rootNode): 
    rootNode.customList = None
newHeap = Heap(5) 
insertNode(newHeap, 4, "Max") 
insertNode(newHeap, 5, "Max") 
insertNode(newHeap, 3, "Max") 
insertNode(newHeap, 1, "Max") 
deleteEntireBP(newHeap)
levelOrderTraversal(newHeap)

Time complexity: O(1), Space complexity: O(1)

Time and Space complexity of Binary Heap

| |
Time complexity | Space complexity | | --- | --- | --- | | Create BP | O(1) | O(N) | | Peek of Heap | O(1) | O(1) | | Size of heap | O(1) | O(1) | | Traversal of heap | O(N) | O(1) | | Insert a node to BP | O(logN) | O(logN) | | Extract a node to BP | O(logN) | O(logN) | | Delete entire BP | O(1) | O(1) |

End

0
Subscribe to my newsletter

Read articles from Fatima Jannet directly inside your inbox. Subscribe to the newsletter, and don't miss out.

heapBinary Search Algorithmbinary heapProgramming BlogsProgramming TipsLearn Code OnlineLearning Journeycodecodingcoding journeyPythonDSAalgorithms

Written by

Fatima Jannet
Fatima Jannet