Home Python Heap Data Structures

Heap Data Structures

Heap is a type of balanced binary tree data structure in which the root-node key is compared to its children, and the data is organized as a result. As previously mentioned, data structures are essential in computer programming for efficiently organizing, managing, and storing data. Any developer’s toolkit should provide data structures as a must-have capability.

This article focuses on recognizing and applying data structures with an emphasis on Heaps in that regard.

What is the definition of a complete binary tree?

A complete binary tree is one in which all levels except the last, i.e., the leaf node, is filled, and all nodes are justified to the left. Aside from the leaf nodes, which can be empty, every node has a maximum of two children. Heaps are created using the heap property, which compares the parent and child node keys.

It’s important to remember that heaps aren’t always sorted; instead, depending on whether it’s a Max or Min Heap, the most significant or most minor element is put on the root node (top). Heap memory is not the same as a heap data structure.

Heaps’ benefits and drawbacks

  • Garbage collection operates on heap memory to free up space used by the object.
  • Since memory can be allocated and removed in any order, heaps are very versatile.
  • Variables can be accessed from anywhere in the world.
  • It assists in deciding the smallest and largest number.

Negative aspects:

  • Heaps need more time to execute than stacks.
  • Since heap memory is used internationally, memory management is more complicated.
  • Heaps take longer to compute than other types of data.

Heaps’ Crucial Operations

When constructing a heap data structure, you’ll need to perform the following operations:

  • Heapify: reorders the elements in a heap to keep the heap property.
  • Insert: inserts an object into a heap while retaining the heap’s heap rights.
  • Delete: deletes a single object from a heap.
  • Extract: returns an item’s value before removing it from the heap.
  • isEmpty: Boolean; returns true if the Boolean is empty, false otherwise.
  • Scale: returns the heap’s size.
  • getMax(): returns the heap’s maximum value.

Heap Data Structure Applications

Heaps help statistics and selection algorithms because they are fast at finding the minimum and maximum elements in an array.

Having the minimum and maximum value from a heap takes O(1) O(1) time (constant time complexity). Heap systems are used to build priority queues. A priority queue is an abstract term similar to “a list” or “a grid,” It can be implemented using a heap or several other methods, much like a list can be implemented using a linked list or an array.

Inserting (insert ()) and deleting (delete ()) each element in the priority queue efficiently takes O (log(n))O(log(n)) time. A heap data structure can combine several already-sorted input streams into a single sorted output stream.

External sorting and streaming results from distributed data, such as a log-structured merge tree, are examples of the need for merging.

The inner loop obtains the min element for the corresponding input stream, replaces it with the next element, and then performs a sift-down heap operation. Another choice is to use the replace function. In fact, using the priority queue’s extract-max and insert functions is much less efficient.

Common algorithms that use heap-implemented priority queues include:

  • The algorithm devised by Prim
  • The algorithm of Dijkstra
  • Heapsort is a sorting algorithm

Max-Heap: In a Max-Heap, the root node’s key must be the greatest of all the keys present in all of its children. For all sub-trees in that Binary Tree, the same property must be valid recursively.

Min-Heap: In a Min-Heap, the root node’s key must be the smallest of all the keys present in all of its children. For all sub-trees in that Binary Tree, the same property must be valid recursively.

This property generates Max Heap since the parent’s value is greater than the value of the child.
A heap can be classified into two categories based on these parameters. When the root node’s value is less than or equal to any of its children, it is called a min-heap.

When the root node’s value is greater than or equal to any of its children, it is called a Max-Heap. Both trees are designed with the same input and in the same order.

Algorithm for Max Heap Construction

To demonstrate how a Max Heap is generated, we’ll use the same example. Creating Min Heap is similar to creating Max Heap, but we use min values instead of max values.

By adding one element at a time, we can derive an algorithm for max heap.

The property of a heap must be preserved at all times. We also assume that we are inserting a node into an already heaped tree when inserting.

Phase 1: Make a new node at the bottom of the heap.

Phase 2: Give the node a new value.

Phase 3: Compare this child node’s value to that of its parent.

Phase 4: If the parent’s value is less than the child’s, exchange them.

Phase 5: Repeat steps 3 and 4 until the Heap property is preserved.

Note that we expect the parent node’s value to be lower than the child node’s in the Min Heap construction algorithm. Thus, we’re going to use the same input sample as before.

Algorithm for Maximum Heap Deletion

Let’s build an algorithm for deleting from the maximum heap.

The Max (or Min) Heap root is permanently deleted to remove the maximum (or minimum) value.

Step 1: Delete the root node first.

Step 2: Transfer the last element from the previous stage to the root.

Step 3: Compare this child node’s value to that of its parent.

Step 4: If the parent’s worth is less than the child’s, exchange them.

Step 5: Repeat steps 3 and 4 until the Heap property is preserved.

# implementation of a Max-Heap data structure in Python

def heapify(arr, n, i):
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2

    if l < n and arr[i] < arr[l]:
        largest = l

    if r < n and arr[largest] < arr[r]:
        largest = r

    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)


def insert(array, newNum):
    size = len(array)
    if size == 0:
        array.append(newNum)
    else:
        array.append(newNum)
        for i in range((size // 2) - 1, -1, -1):
            heapify(array, size, i)


def deleteNode(array, num):
    size = len(array)
    i = 0
    for i in range(0, size):
        if num == array[i]:
            break

    array[i], array[size - 1] = array[size - 1], array[i]

    array.remove(num)

    for i in range((len(array) // 2) - 1, -1, -1):
        heapify(array, len(array), i)

if __name__=='__main__':
    arr = []

    insert(arr, 3)
    insert(arr, 4)
    insert(arr, 9)
    insert(arr, 5)
    insert(arr, 2)

    print("Max-Heap array: " + str(arr))

    deleteNode(arr, 4)
    print("After deleting an element: " + str(arr))
max heap
max heap

How to Make a Min Heap

Since min-heaps are the polar opposite of max-heaps, we can infer that a min-heap’s elements obey the min-heap property.

The parent node’s key is always less than the key of both child nodes.

To make a small heap, we need to do the following:

At the bottom of the heap, create a new child node (last level).

To that node, add the new key and append it to the array.

Move the child up until the heap property is satisfied and you enter the root node.

To remove/delete a root node from a min-heap, do the following:

• Remove the root node from the tree.

• Change the last child's key to base.

• Compare the children of the parent node.

• Swap the parent and child nodes if the parent's value is greater than the child's, and repeat until the heap property is satisfied.
import math
class minHeap:
    def __init__(self):
        self.heap = []
        self.elements = 0

    def insert(self,val):
        if (self.elements >= len(self.heap)):
            self.elements = self.elements + 1
            self.heap.append(val)
            self.__percolateUp(len(self.heap) - 1)
        else:
            self.heap[self.elements] = val
            self.elements = self.elements + 1
            self.__percolateUp(self.elements - 1)


    def getMin(self):
        if (len(self.heap) != 0):
            return self.heap[0]
        return null


    def removeMin(self):
        min = self.heap[0]
        if (self.elements > 1):
            self.heap[0] = self.heap[self.elements - 1]
            self.elements = self.elements - 1
            self.__minHeapify(0)
            return min
        elif (self.elements == 1):
            self.elements = self.elements - 1
            return min
        else:
            return null


    def __percolateUp(self,index):
        parent = math.floor((index - 1) / 2)
        if (index <= 0):
            return
        elif (self.heap[parent] > self.heap[index]):
            tmp = self.heap[parent]
            self.heap[parent] = self.heap[index]
            self.heap[index] = tmp
            self.__percolateUp(parent)



    def __minHeapify(self,index):
        left = (index * 2) + 1
        right = (index * 2) + 2
        smallest = index
        if ((self.elements > left) and (self.heap[smallest] > self.heap[left])):
            smallest = left

        if ((self.elements > right) and (self.heap[smallest] > self.heap[right])):
            smallest = right
        if (smallest != index):
            tmp = self.heap[smallest]
            self.heap[smallest] = self.heap[index]
            self.heap[index] = tmp
            self.__minHeapify(smallest)



    def buildHeap(self,arr):
        self.heap = arr
        self.elements = len(self.heap)
        for i in range(0,len(self.heap) - 1):
            self.__minHeapify(i)


if __name__=='__main__':
    print('The minHeap is ')
    _newHeap = minHeap()
    _newHeap.insert(15)
    _newHeap.insert(5)
    _newHeap.insert(3)
    _newHeap.insert(17)
    _newHeap.insert(10)
    _newHeap.insert(84)
    _newHeap.insert(19)
    _newHeap.insert(6)
    _newHeap.insert(22)
    _newHeap.insert(9)

    print(_newHeap.getMin())
min heap
min-heap

Min Heap to Max Heap Conversion

Let’s take our learning to the next stage by completing a hands-on challenge. The aim is to transform a min heap into a max-heap.

To see how it’s handled, follow along with our code solution.

Implement a function buildMaxHeap(maxHeap) that converts a binary min-heap into a binary max-heap. With maxHeap being an array in the maxHeap format, i.e., the parent is more significant than its children.

Your results should be an array that has been transformed.

maxHeap = [1, 4, 5, 6, 7, 9] is a sample input.

Output Example:

[9,7,5, 6, 4, 1 ] is the outcome.

# implementation program to convert min Heap to max heap

# to heapify a subtree with root at given index
def heapifyToMax(_array, i, n):
    l = 2 * i + 1
    r = 2 * i + 2
    largest = i
    if l < n and _array[l] > _array[i]:
        largest = l
    if r < n and _array[r] > _array[largest]:
        largest = r
    if largest != i:
        _array[i], _array[largest] = _array[largest], _array[i]
        heapifyToMax(_array, largest, n)


# This function basically builds max heap
def buildMaxHeap(_arr, n):
    # Start from bottommost and rightmost
    # internal mode and heapify all
    # internal modes in bottom up way
    for i in range(int((n - 2) / 2), -1, -1):
        heapifyToMax(_arr, i, n)


# function to print an array given the size of the array
def printArray(_arr, size):
    for i in range(size):
        print(_arr[i], end=" ")
    print()


# main method to test max to min heap implementation
if __name__ == '__main__':
    #  Min Heap array representation
    _arr = [1, 4, 5, 6, 7, 9]
    n = len(_arr)

    print("Min Heap _array : ")
    printArray(_arr, n)

    buildMaxHeap(_arr, n)

    print("Max Heap array : ")
    printArray(_arr, n)
min max heap conversion
min max heap conversion

Priority Queue

This is a queue that is prioritized.

The priority queue’s logical order of elements is determined by the elements’ priority, similar to how we insert an element from the back and delete an element from the front in a queue.

The highest priority element will be shifted to the front of the line, while the lowest priority element will be placed to the back.

Consequently, an element that is enqueued at the back of the queue may transfer to the front due to its highest priority.

Let’s assume we have a five-element array: 4, 8, 1, 7, 3, and we need to put all of the elements in the max-priority queue.

Since the priority queue is currently empty, four items will be added first.

Since 8 are greater than 4, when 8 are added, it will be pushed to the front.

Since 1 is the current minimum element in the priority queue, it will stay at the bottom of the priority queue when being inserted.

Since 7 is smaller than 8, it will now be inserted between 8 and 4.

Since 3 is the second lowest element in the priority queue, it will now be inserted before 1.

The priority queue can be implemented in a variety of ways.

Simple Approach: Assume we have items that must be inserted into the priority queue. We may use a list to insert elements in time and sort them to maintain a time-based priority queue.

Efficient Approach: To execute the priority queue, we can use heaps by inserting and deleting each factor in the priority queue will take some time.

Priority queues are divided into two categories based on their heap structure: max-priority queue and min-priority queue.

Let’s concentrate on the Max Priority Queue.

The Max Priority Queue is based on the max heap. Below is the implementation of a priority queue using a queue.

Example 1:

# implementation program for Priority Queue using a Queue
class priorityQueue(object):
	def __init__(self):
		self.queue = []

	def __str__(self):
		return ' '.join([str(i) for i in self.queue])

	# function to check if the queue is empty
	def isQueueEmpty(self):
		return len(self.queue) == 0

	# function to appendElement an element in the queue
	def appendElement(self, data):
		self.queue.append(data)

	# function to pop an element based on Priority
	def deleteElement(self):
		try:
			max = 0
			for i in range(len(self.queue)):
				if self.queue[i] > self.queue[max]:
					max = i
			item = self.queue[max]
			del self.queue[max]
			return item
		except IndexError:
			print()
			exit()

if __name__ == '__main__':
    _queue = priorityQueue()
    _queue.appendElement(12)
    _queue.appendElement(1)
    _queue.appendElement(14)
    _queue.appendElement(7)
    print(_queue)
    print("delete elements from the queue \n")
    while not _queue.isQueueEmpty():
        print("delete element: ",_queue.deleteElement())
priority queue example 1
priority queue example 1

Example 2:

# Code to implement the Max Heap
import sys


class MaxHeap:
	def __init__(self, maxsize):

		self.maxsize = maxsize
		self.size = 0
		self.Heap = [0] * (self.maxsize + 1)
		self.Heap[0] = sys.maxsize
		self.FRONT = 1

	'''
	Function to return the position of parent for the current node
	'''
	def parentPosition(self, pos):
		return pos // 2

	'''
	Function that returns the position of the left child for current node
	'''
	def returnLeftChild(self, pos):

		return 2 * pos

	'''
	Function that returns the position of the right child for the current node
	'''
	def returnRightChild(self, pos):
		return (2 * pos) + 1

	'''
	Function that returns true if the passed node is a leaf node
	'''
	def returnIsLeaf(self, pos):
		if pos >= (self.size // 2) and pos <= self.size:
			return True
		return False

	'''
	Function that swaps two nodes of the heap
	'''
	def swapNodes(self, fpos, spos):
		self.Heap[fpos], self.Heap[spos] = (self.Heap[spos],
											self.Heap[fpos])

	'''
	Function to heapify the current node 
	'''
	def maxHeapify(self, pos):

		# If the node is a non-leaf node and smaller than any of its child
		if not self.returnIsLeaf(pos):
			if (self.Heap[pos] < self.Heap[self.returnLeftChild(pos)] or
					self.Heap[pos] < self.Heap[self.returnRightChild(pos)]):

				# Swap with the left child and heapify the left child
				if (self.Heap[self.returnLeftChild(pos)] >
						self.Heap[self.returnRightChild(pos)]):
					self.swapNodes(pos, self.returnLeftChild(pos))
					self.maxHeapify(self.returnLeftChild(pos))

				# Swap with the right child and heapify the right child
				else:
					self.swapNodes(pos, self.returnRightChild(pos))
					self.maxHeapify(self.returnRightChild(pos))

	'''
	Function that inserts a node into the heap
	'''
	def insertElement(self, element):

		if self.size >= self.maxsize:
			return
		self.size += 1
		self.Heap[self.size] = element

		current = self.size

		while (self.Heap[current] >
			   self.Heap[self.parentPosition(current)]):
			self.swapNodes(current, self.parentPosition(current))
			current = self.parentPosition(current)

	'''
	Function that print's heap contents
	'''
	def printHeap(self):
		for i in range(1, (self.size // 2) + 1):
			print(" PARENT : " + str(self.Heap[i]) +
				  " LEFT CHILD : " + str(self.Heap[2 * i]) +
				  " RIGHT CHILD : " + str(self.Heap[2 * i + 1]))

	'''
	Function to remove and return the maximum element from the heap
	'''
	def extractMaximum(self):

		popped = self.Heap[self.FRONT]
		self.Heap[self.FRONT] = self.Heap[self.size]
		self.size -= 1
		self.maxHeapify(self.FRONT)

		return popped


# code to test the program MaxHeap
if __name__ == "__main__":
	maxHeap = MaxHeap(15)
	maxHeap.insertElement(22)
	maxHeap.insertElement(3)
	maxHeap.insertElement(5)
	maxHeap.insertElement(17)
	maxHeap.insertElement(19)
	maxHeap.insertElement(10)
	maxHeap.insertElement(6)
	maxHeap.insertElement(84)
	maxHeap.insertElement(9)

	maxHeap.printHeap()

	print("\nThe Maximum value in the heap is: " + str(maxHeap.extractMaximum()))
priority queue example 2
priority queue example 2

In the last example, the indexing starts from 1 to make the implementation easy. Below are the various Max Heap operations demonstrated in this example.

getMaximum(): It returns the root element of Max Heap. The Time Complexity of this operation is O(1).

extractMaximum(): It removes the MaxHeap’s maximum element. Time Complexity of this Operation is O(Log n) as this operation needs to maintain the heap property through calling the maxHeapify()) after removing the root.

insertElement (): Inserts a new key and takes O(Log n) time complexity. We add a new key at the end of the tree. If the new key is smaller than its parent, then there is no need to do anything. Otherwise, traverse up to fix the heap’s violated property.

You may also like

Leave a Comment

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More