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.
<div class="wp-block-codemirror-blocks-code-block code-block">
<pre># 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))</pre>
</div>
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.
<div class="wp-block-codemirror-blocks-code-block code-block">
<pre>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())
</pre>
</div>
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.
<div class="wp-block-codemirror-blocks-code-block code-block">
<pre># 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)</pre>
</div>
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:
<div class="wp-block-codemirror-blocks-code-block code-block">
<pre># 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())
</pre>
</div>
Example 2:
<div class="wp-block-codemirror-blocks-code-block code-block">
<pre># 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()))</pre>
</div>
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.
