DEV Community

Cover image for Your complete guide to Heap data structure!
Aya Bouchiha
Aya Bouchiha

Posted on • Updated on

Your complete guide to Heap data structure!

#algorithms #computerscience #codenewbie #beginners

Hi, I'm Aya Bouchiha, in this beautiful day, I'm going to explain the Heap data structure.
#day_22

Definition of Heap

Heap: is a complete binary tree (types of a binary tree) (which each node has at most two children and All the leaves should lean towards the left) where the root node is compared with its children and arrange accordingly.

Example of complete binary tree

complete binary tree in data structure Aya Bouchiha

Example of incomplete binary tree

binary tree in data structure Aya Bouchiha Heap

Types of Heap

1. Max-heap

The key of every node is smaller than or equal its parent

arr[parent] >= arr[i]

Example of max-heap

max heap in data structure Aya Bouchiha

2. Min-heap

The key of every node is greater than or equal its parent

arr[parent] <= arr[i]

Example of min-heap

min heap un data structure Aya Bouchiha

Application of Heap

  • Heap sort algorithm
  • Order statistics Getting The minimum value or the maximum value in a constant time
  • Graph algorithms like Prim's Algorithm and Dijkstra's algorithm
  • Priority Queue

Space and Time complexity of Heap

The space complexity of the heap is O(n)

insertion (push) deletion (pop) peek
O(log n) O(log n) O(1)

Heap array implementation

let's take this example of max-heap:
the index of each node is between parentheses ( ):

          15(0)
      /          \
 (1) 9            13 (2)
    /  \         /
(3)5  (4)7   (5)11
Enter fullscreen mode Exit fullscreen mode 
arr = [15, 9, 13, 5, 7, 11]
Enter fullscreen mode Exit fullscreen mode

the implementation can be done by:

  • making the root the first element in the array arr[0] = root
  • Parent node: arr[(i - 1) // 2]
  • Left-child: arr[2 * i + 1]
  • Right-child: arr[2 * i + 2] 
class MinHeap:
    def __init__(self):
        self.heap = []
        self.heap_size = 0

    def getParentNodeIndex(self, i: int) -> int:
        return (i-1)//2

    def getLeftChildNodeIndex(self, i: int) -> int:
        return 2*i+1

    def getRightChildNodeIndex(self, i: int) -> int:
        return 2*i+2

    def hasParent(self, i: int) -> bool:
        # cheking if a node has a parent
        return self.getParentNodeIndex(i) < len(self.heap)

    def hasLeftChild(self, i: int) -> bool:
        # cheking if a node has a left child
        return self.getLeftChildNodeIndex(i) < len(self.heap)

    def hasRightChild(self, i: int) -> bool:
        # cheking if a node has a right child
        return self.getRightChildNodeIndex(i) < len(self.heap)

    def getMinValue(self) -> int:
        """
            time complexity => O(1)
        """
        return self.heap[0]

    def printAll(self):
        print(self.heap)
Enter fullscreen mode Exit fullscreen mode

Insertion (push) in Heap

1. Approach of insertion

  • Increase the size of the heap to add a new element
  • The heap is a complete binary tree that's why the new element should lean towards the left, which means, in array representation, we insert the element at the end of the array.
  • Heap must satisfy the heap-order property, that's why we should Heapify or bubble up the new element, Heapify or bubbling up is swapping the new element with its parent until
    • its parent is greater than or equal to it in a max-heap.
    • its parent is smaller than or equal to it in min-heap.

1. Explanation of insertion

For better understanding, let's take an example:
  we want to insert 1 in this min-heap

        3 (0)
      /   \
 (1) 5     10 (2)
   / 
  9 (3)
Enter fullscreen mode Exit fullscreen mode 
  [3, 5, 10, 9]
Enter fullscreen mode Exit fullscreen mode
  1. Insert the new Element at the end of the array 
         3 (0)
       /   \
 (1)  5     10 (2)
    /  \ 
(3)9 (4)1
Enter fullscreen mode Exit fullscreen mode 
  heap_size += 1
  arr = [3, 5, 10, 9, 1]
Enter fullscreen mode Exit fullscreen mode
  1. Bubble up the new element
  • Since 1 < 5, swap them, so: 
         3 (0)
       /   \
 (1)  1     10 (2)
    /  \ 
(3)9 (4)5
Enter fullscreen mode Exit fullscreen mode 
  arr = [3, 5, 10, 9, 1]
  newElementIndex = len(arr) - 1 # 4
  # the index of the parent of the new element
  ParentIndex = (newElementIndex - 1) // 2 # (4-1)//2 = 1 
  # 1 < 5 
  if arr[newElementIdx] < arr[ParentIdx]:
      # swap(1, 5)
      arr[newElementIdx], arr[ParentIdx] = arr[ParentIdx], arr[newElementIdx]
Enter fullscreen mode Exit fullscreen mode

the array will be:

arr = [3, 1, 10, 9, 5]
Enter fullscreen mode Exit fullscreen mode
  • Hence 1 < 3, swap them, so: 
         1 (0)
       /   \
 (1)  3     10 (2)
    /  \ 
(3)9 (4)5
Enter fullscreen mode Exit fullscreen mode

we'll do the same process for 1 and 3 like (1 and 5) so the array will be

arr = [1, 3, 10, 9, 5]
Enter fullscreen mode Exit fullscreen mode

3. Implementation of insertion in python

the implementation of bubble up or heapify function in python 

    def bubbleUp(self, i: int):
        parentIndex = self.getParentNodeIndex(i)
        if parentIndex < 0:
            parentIndex = 0 
        # Loops until it reaches a leaf node
        while(i > 0 and self.heap[i] < self.heap[self.getParentNodeIndex(i)]): 
            # Swap the elements
            self.heap[i], self.heap[self.getParentNodeIndex(i)] = self.heap[self.getParentNodeIndex(i)], self.heap[i]
            i = self.getParentNodeIndex(i)
Enter fullscreen mode Exit fullscreen mode

the implementation of insert function in python 

    def insert(self, value: int):
        self.heap_size += 1
        # insert the element at the end
        self.heap.append(value) 
        # bubble up the new element
        self.bubbleUp(len(self.heap) - 1)
Enter fullscreen mode Exit fullscreen mode

Deletion in Heap

1. Approach of Deletion

The standard deletion operation on Heap is deleting the root which is the maximum value of the max-heap, and the minimum value of the in-heap.

  • Decrease the size of the heap to delete the element
  • Swap the root with the last element
  • Pop (delete) last element of the array
  • Heap must satisfy the heap-order property, that's why we should bubble-down (also known as heapify, percolate-down, sift-down, sink-down, trickle-down, heapify-down, cascade-down, extract-min or extract-max, or down-heap) the new element, bubble-down is swapping the new element with one of its children until
    • the child is smaller than or equal to it in a max-heap.
    • the child is greater than or equal to it in a min-heap.

1. Explanation of deletion

For better understanding, let's take an example:
  we want to delete 3 in this min-heap

        3 (0)
      /   \
 (1) 5     10 (2)
   / 
  9 (3)
Enter fullscreen mode Exit fullscreen mode 
  [3, 5, 10, 9]
Enter fullscreen mode Exit fullscreen mode
  1. Swap the root with the last element 
         9 (0)
       /   \
 (1)  5     10 (2)
    /  
(3)3
Enter fullscreen mode Exit fullscreen mode 
  arr = [9, 5, 10, 3]
Enter fullscreen mode Exit fullscreen mode
  1. Delete the last element and decrease the size of the array 
         9 (0)
       /   \
 (1)  5     10 (2)
Enter fullscreen mode Exit fullscreen mode 
  arr = [9, 5, 10, 3]
  heap_size -= 1
  arr.pop()
Enter fullscreen mode Exit fullscreen mode

so the array will be

  arr = [9, 5, 10]
Enter fullscreen mode Exit fullscreen mode
  1. Bubble down the root
  • Since 9 > 5, swap them, so: 
         5 (0)
       /   \
 (1)  9     10 (2)
Enter fullscreen mode Exit fullscreen mode 
  arr = [5, 9, 10]
Enter fullscreen mode Exit fullscreen mode

3. Implementation of deletion in python

Bubble down implementation in python 

    def bubbleDown(self):
        # the index of the root => 0
        i = 0
        while True:
            smallest = None

            leftChildIndex = self.getLeftChildNodeIndex(i)
            rightChildIndex =  self.getRightChildNodeIndex(i)
            #  if the node has not any child 
            if (not self.hasLeftChild(i) and not self.hasRightChild(i)):
                break
            # if the node has only a left child
            elif (not self.hasRightChild(i)):
                # the smallest variable will be the index of the left child
                smallest = leftChildIndex
            # if the node has only a right child
            elif (not self.hasLeftChild(i)):
                # the smallest variable will be the index of the right child
                smallest = rightChildIndex
            # if the node has 2 children
            else:
                # the smallest variable will be the smallest value of the 2 children
                smallest = rightChildIndex if self.heap[rightChildIndex] < self.heap[leftChildIndex] else leftChildIndex            
            # if the node's value is greater than its one of children
            if (self.heap[i] > self.heap[smallest]):
                # swap the node with its child
                self.heap[i], self.heap[smallest] = self.heap[smallest], self.heap[i]
                # the i variable will be the index of the smallest value of the two children
                i = smallest
            # if the node's value is smaller than its one of children
            else:
                break
        return
Enter fullscreen mode Exit fullscreen mode

delete implementation in python 

    def delete(self):
        # if the size the heap is one or the heap is empty(size = 0)
        if self.heap_size <= 1:
            self.heap = []
            return
        # replace last element with the root
        self.heap[self.heap_size - 1], self.heap[0] = self.heap[0], self.heap[self.heap_size - 1]
        # decrease the size of heap
        self.heap_size -= 1
        # delete last element
        self.heap.pop()
        self.bubbleDown()
Enter fullscreen mode Exit fullscreen mode

Heap implementation in python (Final code) 

class MinHeap:
    def __init__(self):
        self.heap = []
        self.heap_size = 0

    def getParentNodeIndex(self, i: int) -> int:
        return (i-1)//2

    def getLeftChildNodeIndex(self, i: int) -> int:
        return 2*i+1

    def getRightChildNodeIndex(self, i: int) -> int:
        return 2*i+2

    def hasParent(self, i: int) -> bool:
        # cheking if a node has a parent
        return self.getParentNodeIndex(i) < len(self.heap)

    def hasLeftChild(self, i: int) -> bool:
        # cheking if a node has a left child
        return self.getLeftChildNodeIndex(i) < len(self.heap)

    def hasRightChild(self, i: int) -> bool:
        # cheking if a node has a right child
        return self.getRightChildNodeIndex(i) < len(self.heap)

    def getMinValue(self) -> int:
        """
            time complexity => O(1)
        """
        return self.heap[0]

    def insert(self, value: int):
        self.heap_size += 1
        # insert the element at the end
        self.heap.append(value) 
        # bubble up the new element
        self.bubbleUp(len(self.heap) - 1)

    def bubbleUp(self, i: int):
        parentIndex = self.getParentNodeIndex(i)
        if parentIndex < 0:
            parentIndex = 0 
        # Loops until it reaches a leaf node
        while(i > 0 and self.heap[i] < self.heap[self.getParentNodeIndex(i)]): 
            # Swap the elements
            self.heap[i], self.heap[self.getParentNodeIndex(i)] = self.heap[self.getParentNodeIndex(i)], self.heap[i]
            i = self.getParentNodeIndex(i) 

    def delete(self):
        # if the size the heap is one or the heap is empty(size = 0)
        if self.heap_size <= 1:
            self.heap = []
            return
        # replace last element with the root
        self.heap[self.heap_size - 1], self.heap[0] = self.heap[0], self.heap[self.heap_size - 1]
        # decrease the size of heap
        self.heap_size -= 1
        # delete last element
        self.heap.pop()
        self.bubbleDown()

    def bubbleDown(self):
        # the index of the root => 0
        i = 0
        while True:
            smallest = None

            leftChildIndex = self.getLeftChildNodeIndex(i)
            rightChildIndex =  self.getRightChildNodeIndex(i)
            #  if the node has not any child 
            if (not self.hasLeftChild(i) and not self.hasRightChild(i)):
                break
            # if the node has only a left child
            elif (not self.hasRightChild(i)):
                # the smallest variable will be the index of the left child
                smallest = leftChildIndex
            # if the node has only a right child
            elif (not self.hasLeftChild(i)):
                # the smallest variable will be the index of the right child
                smallest = rightChildIndex
            # if the node has 2 children
            else:
                # the smallest variable will be the smallest value of the 2 children
                smallest = rightChildIndex if self.heap[rightChildIndex] < self.heap[leftChildIndex] else leftChildIndex            
            # if the node's value is greater than its one of children
            if (self.heap[i] > self.heap[smallest]):
                # swap the node with its child
                self.heap[i], self.heap[smallest] = self.heap[smallest], self.heap[i]
                # the i variable will be the index of the smallest value of the two children
                i = smallest
            # if the node's value is smaller than its one of children
            else:
                break
        return

    def printAll(self):
        print(self.heap)

my_heap = MinHeap()
my_heap.insert(5)
my_heap.insert(10)
my_heap.insert(1)
my_heap.insert(2)
my_heap.insert(3)
my_heap.insert(4)
#      1
#    /  \ 
#   2     4
#  / \   /
# 10  3  5
my_heap.printAll()
my_heap.delete()
my_heap.printAll()
#      2
#    /  \ 
#   3     4
#  / \   
# 10  5  
print(my_heap.heap_size) # 5
print(my_heap.getMinValue()) # 2
Enter fullscreen mode Exit fullscreen mode

References and useful resources

if you have any suggestions for the next posts or any questions you can contact me in telegram

Happy coding :)
#day_22

Top comments (2)

Collapse
 
aminmansuri profile image
hidden_dude •

Add the option to initialize it with an array of values, because the greatest benefit of a heap is the ability to create one in O(N) time from an array of values.

Also, in real heaps you have value/priority pairs. The heap orders by priority but the actual value is can be some other object. (Unless you're simply implementing a HeapSort on numbers)

Collapse
 
ayabouchiha profile image
Aya Bouchiha •

Thank you a lot for your feedback 🙏🙏

Read next

suzuki0430 profile image

Avoiding Connection Pinning in Lambda and RDS Proxy with NestJS and Proxy Splitting

Atsushi Suzuki -

dumebii profile image

API Documentation Tools: Using Hoppscotch for API Documentation

Dumebi Okolo -

balrajola profile image

Best Practices for Code Reviews That Foster Team Collaboration

balrajOla -

msnmongare profile image

M-Pesa Express (STK Push) API Guide

Sospeter Mong'are -