Related Topics
Data Structure
class MinHeap:
def __init__(self):
self.heap = []
def parent(self, i):
return (i - 1) // 2
def left_child(self, i):
return 2 * i + 1
def right_child(self, i):
return 2 * i + 2
def swap(self, i, j):
self.heap[i], self.heap[j] = self.heap[j], self.heap[i]
def heapify_up(self, i):
while i > 0 and self.heap[i] < self.heap[self.parent(i)]:
self.swap(i, self.parent(i))
i = self.parent(i)
def heapify_down(self, i):
while (left := self.left_child(i)) < len(self.heap):
right = self.right_child(i)
min_child = left if right >= len(self.heap) or self.heap[left] < self.heap[right] else right
if self.heap[i] <= self.heap[min_child]:
break
self.swap(i, min_child)
i = min_child
def insert(self, val):
self.heap.append(val)
self.heapify_up(len(self.heap) - 1)
def extract_min(self):
if len(self.heap) == 0:
return None
min_val = self.heap[0]
self.swap(0, len(self.heap) - 1)
self.heap.pop()
self.heapify_down(0)
return min_val
This implementation uses a list to store the heap and provides methods to insert elements into the heap and extract the minimum value. The heapify_up and heapify_down methods are used to maintain the heap property. The insert method adds a new element to the end of the list and then performs heapify_up to ensure that the new element is in the correct position. The extract_min method removes the minimum element (which is always at the root of the heap) by swapping it with the last element in the list, removing the last element, and then performing heapify_down to restore the heap property.
To implement a max heap, you can simply reverse the comparison operators (< becomes > and vice versa) in the heapify_upandheapify_down` methods.
def insert(heap, value):
heap.append(value)
index = len(heap) - 1
while index > 0:
parent_index = (index - 1) // 2
if heap[index] < heap[parent_index]:
heap[index], heap[parent_index] = heap[parent_index], heap[index]
index = parent_index
else:
break
The heap parameter is a list representing the heap, and the value parameter is the new element to be inserted. The append() method adds the new element to the end of the list. The index variable is initialized to the index of the new element, and the loop continues until the heap property is restored. The parent_index variable is calculated using integer division, and the comparison and swap are performed if necessary. The loop ends when the new element is in the correct position in the heap.
def heapify(arr, n, i):
# Find the largest element among root, left child and right child
largest = i # Initialize largest as root
l = 2 * i + 1 # left child = 2*i + 1
r = 2 * i + 2 # right child = 2*i + 2
if l < n and arr[l] > arr[largest]:
largest = l
if r < n and arr[r] > arr[largest]:
largest = r
# If root is not the largest element, swap with largest
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
# Heapify the affected sub-tree
heapify(arr, n, largest)
def heap_sort(arr):
n = len(arr)
# Build a max heap
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
# Extract elements one by one
for i in range(n - 1, 0, -1):
# Move current root to end
arr[i], arr[0] = arr[0], arr[i]
# Call max heapify on the reduced heap
heapify(arr, i, 0)
return arr
The heapify function is used to maintain the heap property, and the heap_sort function builds a max heap from the input array, and then repeatedly extracts the maximum element and places it at the end of the array until the entire array is sorted. The time complexity of heap sort is O(n log n), and it has the advantage of being an in-place sort, meaning it does not require extra space beyond the input array.
Popular Category
Topics for You
Go through our study material. Your Job is awaiting.