HEAP Data Structure – A Complete Guide [Python Code]

An introduction to Heap

In computer science, a heap is a tree-based data structure that is commonly used to implement priority queues. The heap is a type of binary tree i.e. each parent node can have only two children (left and right). All levels of the tree are completely filled, except possibly the last level, which is filled from left to right. In this article, we will explore the concept of heap data structure, its implementation, and the various operations that can be performed on a heap.

What is a heap?

A heap is a data structure that is used to store a collection of elements, and the elements are arranged in a way that satisfies the heap property. The heap property is the property that states that for every node in the heap, the key of the parent node is less than or equal to the key of the child node. The keys can be any type that is comparable, such as integers or strings.

Types of heaps:

There are two types of heaps: max heap and min heap. In a max heap, the value of each node is greater than or equal to the values of its children whereas, in a min heap, the value of each node is less than or equal to the values of its children. Therefore, the first node in the “max heap” always returns the highest value while in the min heap, it returns the lowest value.

Types of Heap Data Structure

Implementation:

A heap can be implemented using an array or a tree data structure [as shown in the above picture]. The array implementation is simpler and more efficient in terms of memory usage. The tree implementation, on the other hand, is more flexible and allows for more efficient insertion and deletion operations.

Here, in this article, we are going to use the array data structure of python to represent the heap data structure. Following are some rules, how
In the array implementation, the heap is represented as an array where the first element is the root of the tree, the second and third elements are the children of the root, and so on. For a given node at index i, its left child is located at index 2i+1 , and its right child is located at index 2i+2. The parent of a node at index I is located at the index floor((i-1)/2).

Operations performed on a Heap:

The main operations that can be performed on a heap are insertion or deletion. One more operation which is retrieval can be performed. As explained above, this operation returns the very first value stored in a heap. In min heap, the value stored as a first node, will be the lowest among all but in max heap it will be the highest value.

Insertion:

To insert an element into a heap, we add the element to the end of the array or the bottom of the tree, and then we compare the key of the element with the key of its parent. If the key of the element is greater than the key of its parent in a max heap, or less than the key of its parent in a min heap, we swap the element with its parent, and we repeat the process until the heap property is satisfied.

Deletion:

To delete the minimum or maximum element from a heap, we remove the root of the tree, which is the minimum or maximum element depending on whether the heap is a min heap or a max heap. We then replace the root with the last element in the array or the bottom of the tree, and we compare the key of the new root with the keys of its children. If the key of the new root is less than the keys of its children in a max heap, or greater than the keys of its children in a min heap, we swap the new root with the larger or smaller child, and we repeat the process until the heap property is satisfied.

Retrieval:

To retrieve the minimum or maximum element from a heap, we simply return the root of the tree, which is the minimum or maximum element depending on whether the heap is a min heap or a max heap.

Python Code to implement minHeap Class

class MinimumHeap:
    def __init__(self, array):
        self.heap = self.__buildHeap(array)

    # private methods used within this class
    def __buildHeap(self, array):
        parentNodeIdx = (len(array) - 2) // 2
        for idx in reversed(range(parentNodeIdx + 1)):
            self.__moveDown(array, idx, len(array) - 1)
        return array
       
    def __moveUp(self, heap, startIdx):
        parentIdx = (startIdx - 1) // 2
        while startIdx > 0 and heap[startIdx] < heap[parentIdx]:
            heap[startIdx], heap[parentIdx] = heap[parentIdx], heap[startIdx]
            startIdx = parentIdx
            parentIdx = (startIdx - 1) // 2
    
    def __moveDown(self, heap, startIdx, endIdx):
        childOneIdx = startIdx * 2 + 1
        while childOneIdx <= endIdx:
            if (startIdx * 2 + 2) <= endIdx:
                childTwoIdx = startIdx * 2 + 2
            else:
                childTwoIdx = -1
            if childTwoIdx != -1 and heap[childTwoIdx] < heap[childOneIdx]:
                possibleSwapIdx = childTwoIdx
            else:
                possibleSwapIdx = childOneIdx
            if heap[possibleSwapIdx] < heap[startIdx]:
                heap[startIdx], heap[possibleSwapIdx] = heap[possibleSwapIdx], heap[startIdx]
                startIdx = possibleSwapIdx
                childOneIdx = startIdx * 2 + 1
            else:
                return

    # public methods used to add, get and 
    # insert a new item in the heap

    def insert(self, item):
        self.heap.append(item)
        self.__moveUp(self.heap, len(self.heap) - 1)

    def remove(self):
        lastIdx = len(self.heap) - 1
        self.heap[0], self.heap[lastIdx] = self.heap[lastIdx], self.heap[0]
        self.heap.pop()
        self.__moveDown(self.heap, 0, len(self.heap) - 1)
    
    # returns heapified array
    def getHeapArray(self):
        return self.heap

    # returns minimum value
    def getMinValue(self):
        return self.heap[0]

Python Code to implement maxHeap Class

For creating a maxHeap data structure there is a very minor change, you need to make in the above code. While inserting a new element, instead of moving the smaller element up, you should be moving the bigger element up. Similarly, while moving down, instead of moving bigger elements down, you need to move smaller elements down. These are the only two changes and the rest are going to be exactly the same.

class MaximumHeap:
    def __init__(self, array):
        self.heap = self.__buildHeap(array)

    # private methods used within this class
    def __buildHeap(self, array):
        parentNodeIdx = (len(array) - 2) // 2
        for idx in reversed(range(parentNodeIdx + 1)):
            self.__moveDown(array, idx, len(array) - 1)
        return array
       
    def __moveUp(self, heap, startIdx):
        parentIdx = (startIdx - 1) // 2
        while startIdx > 0 and heap[startIdx] > heap[parentIdx]:
            heap[startIdx], heap[parentIdx] = heap[parentIdx], heap[startIdx]
            startIdx = parentIdx
            parentIdx = (startIdx - 1) // 2
    
    def __moveDown(self, heap, startIdx, endIdx):
        childOneIdx = startIdx * 2 + 1
        while childOneIdx <= endIdx:
            if (startIdx * 2 + 2) <= endIdx:
                childTwoIdx = startIdx * 2 + 2
            else:
                childTwoIdx = -1
            if childTwoIdx != -1 and heap[childTwoIdx] > heap[childOneIdx]:
                possibleSwapIdx = childTwoIdx
            else:
                possibleSwapIdx = childOneIdx
            if heap[possibleSwapIdx] > heap[startIdx]:
                heap[startIdx], heap[possibleSwapIdx] = heap[possibleSwapIdx], heap[startIdx]
                startIdx = possibleSwapIdx
                childOneIdx = startIdx * 2 + 1
            else:
                return

    # public methods used to add, get and 
    # insert a new item in the heap

    def insert(self, item):
        self.heap.append(item)
        self.__moveUp(self.heap, len(self.heap) - 1)

    def remove(self):
        lastIdx = len(self.heap) - 1
        self.heap[0], self.heap[lastIdx] = self.heap[lastIdx], self.heap[0]
        self.heap.pop()
        self.__moveDown(self.heap, 0, len(self.heap) - 1)
    
    # returns heapified array
    def getHeapArray(self):
        return self.heap

    # returns minimum value
    def getMinValue(self):
        return self.heap[0]

Print Heapified array in Tree structure

In the above implementation, the class will return heapified array which will not be easy to visualize in a tree-like structure. Therefore, I have created a simple but not so good function which prints your heapified array in a tree structure in your console.

    # print heapified array in tree structure
    def getHeapTree(self):
        k = level = 0
        tree = ""
        size = len(self.heap) - 1
        lSize = int(math.floor(math.log(size, 2))) + 1
        totalSpace = (2**lSize)*2
        while k <= size:
            levelMax = 2**level
            for l in range(1, levelMax+1):
                tree = tree + " "*int(totalSpace/(2**level + 1)) + str(self.heap[k])
                k = k + 1
                if k > size:
                    break
            level += 1
            tree = tree + "\n\n"
        return tree

Here is the result of the above function for minHeap and maxHeap structured data.

Print - Heapified data in Tree Structure