This Python program implements a ternary heap, which is a type of min-heap where each parent node has up to three child nodes.
A Ternary Heap is a variant of a binary heap, a fundamental data structure used in computer science for implementing priority queues. While a binary heap organizes its elements in a binary tree structure where each node has at most two children (left and right), a ternary heap allows each node to have up to three children. This variation can sometimes offer performance advantages in certain scenarios.
Problem Statement
Design and implement a Ternary Heap data structure in python.
Python Program to Implement Ternary Heap
class TernaryHeap: def __init__(self): self.heap = [] def insert(self, value): self.heap.append(value) self.sift_up(len(self.heap) - 1) def extract_min(self): if not self.heap: return None if len(self.heap) == 1: return self.heap.pop() # Swap the last element with the root (minimum element) min_value = self.heap[0] last_value = self.heap.pop() self.heap[0] = last_value # Sift down to maintain the heap property self.sift_down(0) return min_value def sift_up(self, index): while index > 0: parent_index = (index - 1) // 3 if self.heap[index] < self.heap[parent_index]: self.heap[index], self.heap[parent_index] = self.heap[parent_index], self.heap[index] index = parent_index else: break def sift_down(self, index): while True: left_child_index = 3 * index + 1 middle_child_index = 3 * index + 2 right_child_index = 3 * index + 3 smallest = index if ( left_child_index < len(self.heap) and self.heap[left_child_index] < self.heap[smallest] ): smallest = left_child_index if ( middle_child_index < len(self.heap) and self.heap[middle_child_index] < self.heap[smallest] ): smallest = middle_child_index if ( right_child_index < len(self.heap) and self.heap[right_child_index] < self.heap[smallest] ): smallest = right_child_index if smallest != index: self.heap[index], self.heap[smallest] = self.heap[smallest], self.heap[index] index = smallest else: break def peek_min(self): if not self.heap: return None return self.heap[0] def is_empty(self): return len(self.heap) == 0 def size(self): return len(self.heap) # Example usage: heap = TernaryHeap() heap.insert(5) heap.insert(2) heap.insert(9) heap.insert(1) heap.insert(6) print("Minimum element:", heap.extract_min()) # Output: Minimum element: 1 print("Minimum element:", heap.extract_min()) # Output: Minimum element: 2
How it Works
1. Insertion:
- When you insert a new element into a Ternary Heap, you add it as a leaf node at the leftmost available position in the last level of the tree.
- After inserting the element, you may need to ensure that the heap property is maintained. To do this, you perform a “sift-up” operation:
- Compare the newly inserted element with its parent (the parent is the node at index
(i-1)//3
if the new element is at indexi
). - If the newly inserted element is smaller (for a min-heap) than its parent, swap them.
- Repeat this process until the element is in its correct position, or until you reach the root of the heap.
- Compare the newly inserted element with its parent (the parent is the node at index
2. Extraction (Extracting the Minimum Element):
- To extract the minimum element from a min-heap (or maximum from a max-heap), you typically take the element at the root, which is guaranteed to be the smallest (or largest) element in the heap.
- After removing the root, you need to ensure that the heap property is preserved. To do this, you perform a “sift-down” operation:
- Replace the root with the last leaf node in the heap.
- Compare this new root with its children (up to three children in a ternary heap).
- Swap the root with the smallest child if it is larger than that child (for a min-heap). Repeat this process until the heap property is satisfied for all nodes.
3. Peek (Viewing the Minimum Element):
- To peek at the minimum element (or maximum for a max-heap) without removing it, you simply look at the root of the heap. This operation has a time complexity of O(1) because you don’t need to perform any swaps or adjustments.
4. Is Empty:
- To check if the Ternary Heap is empty, you can simply check if the underlying array or list is empty.
5. Size:
- To determine the number of elements in the Ternary Heap, you can count the elements in the underlying array or list.
Input/ Output
![This Python program implements a ternary heap, which is a type of min-heap where each parent node has up to three child nodes.](https://developerpublish.com/wp-content/uploads/2023/09/image-6.png)