Binary Heap
A binary heap represents a complete binary tree with a special property called the heap property. In a binary heap, for every node “i” other than the root, the value of the node is greater than or equal to the values of its parent nodes. This property is known as a max heap. Alternatively, for a min heap, the value of the node is less than or equal to the values of its parent nodes.
Binary heaps are commonly used to implement priority queues, where elements with higher priorities are dequeued before elements with lower priorities.
Key characteristics of a binary heap include:
Shape Property: A binary heap is a complete binary tree, meaning all levels of the tree are fully filled except possibly for the last level, which is filled from left to right.
Heap Property: In a max heap, for any node “i” at index “i” in the array representation, the value of the node is greater than or equal to the values of its parent node. In a min heap, the value of the node is less than or equal to the values of its parent node.
Binary heaps are typically implemented using an array. The parent-child relationship is maintained by storing elements in the array in a specific order. For a node at index “i”, its left child is located at index 2i, and its right child is located at index 2i+1.
Binary heaps support efficient insertion and extraction of the maximum (or minimum) element, both with a time complexity of O(log N).
Implementation:
Get Jim Tseng’s stories in your inbox
Join Medium for free to get updates from this writer.
Define a binary heap.
- Time complexity: O(1), Space Complexity: O(n)
class Heap:
def __init__(self, size):
self.customList = (size+1) * [None]
self.heapSize = 0
self.maxSize = size + 1Create, Peek, and size of the heap on binary heap
- Peek: Time complexity: O(1), Space Complexity: O(1)
- Size of Heap: Time complexity: O(1), Space Complexity: O(1)
- Traversal: Time complexity: O(n), Space Complexity: O(1)
# Peek method
def peekofHeap(rootNode):
if not rootNode:
return
else:
return rootNode.customList[1]
# Size of binary heap
def sizeofHeap(rootNode):
if not rootNode:
return rootNode.heapSize
# Traversal
def LevelOrderTraversal(rootNode):
if not rootNode:
return
else:
for i in range(1, rootNode.heapSize+1):
print(rootNode.customList[i])Insert a node in the binary heap.
- Time complexity: O(logN), Space Complexity: O(logN)
def heapifyTreeInsert(rootNode, index, heapType):
parentIndex = int(index/2)
if index <= 1:
return
if heapType == "Min":
if rootNode.customList[index] < rootNode.customList[parentIndex]:
rootNode.customList[index], rootNode.customList[parentIndex] = rootNode.customList[parentIndex], rootNode.customList[index]
heapifyTreeInsert(rootNode, parentIndex, heapType)
elif heapType == "Max":
if rootNode.customList[index] > rootNode.customList[parentIndex]:
rootNode.customList[index], rootNode.customList[parentIndex] = rootNode.customList[parentIndex], rootNode.customList[index]
heapifyTreeInsert(rootNode, parentIndex, heapType)
# 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[heapSize + 1] = nodeValue
rootNode.heapSize += 1
heapifyTreeInsert(rootNode, rootNode.heapSize, heapType)
return "The value has been inserted."Extract a node from the binary heap.
- Time complexity: O(logN), Space Complexity: O(logN)
def heapifyTreeExtract(rootNode, index, heapType):
leftIndex = index * 2
rightIndex = index * 2 + 1
swapChild = 0
# Base case: If the left child index is greater than the heap size, it means there are no child nodes, so no further operation is required. Simply return.
if rootNode.heapSize < leftIndex:
return
# Base case: If the left child index is equal to the heap size, it means only the left child node exists. Process the last node.
elif rootNode.heapSize == leftIndex:
if heapType == "Min":
if rootNode.customList[index] > rootNode.customList[leftIndex]:
# If the parent node is greater than the left child node, swap their values.
temp = rootNode.customList[index]
rootNode.customList[index] = rootNode.customList[leftIndex]
rootNode.customList[leftIndex] = temp
return
else:
if rootNode.customList[index] < rootNode.customList[leftIndex]:
# If the parent node is smaller than the left child node, swap their values.
temp = rootNode.customList[index]
rootNode.customList[index] = rootNode.customList[leftIndex]
rootNode.customList[leftIndex] = temp
return
else:
if heapType == "Min":
if rootNode.customList[leftIndex] < rootNode.customList[rightIndex]:
swapChild = leftIndex
else:
swapChild = rightIndex
if rootNode.customList[index] > rootNode.customList[swapChild]:
# If the parent node is greater than the smaller child node, swap their values.
temp = rootNode.customList[index]
rootNode.customList[index] = rootNode.customList[swapChild]
rootNode.customList[swapChild] = temp
else:
if rootNode.customList[leftIndex] > rootNode.customList[rightIndex]:
swapChild = leftIndex
else:
swapChild = rightIndex
if rootNode.customList[index] < rootNode.customList[swapChild]:
# If the parent node is smaller than the larger child node, swap their values.
temp = rootNode.customList[index]
rootNode.customList[index] = rootNode.customList[swapChild]
rootNode.customList[swapChild] = temp
# Recursively perform heapifyTreeExtract on the swapped child node
heapifyTreeExtract(rootNode, swapChild, heapType)def extractNode(rootNode, heapType):
# Check if the heap is empty
if rootNode.heapSize == 0:
return
else:
# Extract the root node (topmost element)
extractedNode = rootNode.customList[1]
# Replace the root node with the last element in customList
rootNode.customList[1] = rootNode.customList[rootNode.heapSize]
rootNode.customList[rootNode.heapSize] = None
rootNode.heapSize -= 1
# Perform heapifyTreeExtract on the root node to maintain the heap property
heapifyTreeExtract(rootNode, 1, heapType)
# Return the extracted node
return extractedNodeDelete the entire binary heap.
- Time complexity: O(1), Space Complexity: O(1)
def deleteEntireBP(rootNode):
rootNode.customList = None
