|
Ak-ary heap is also called n-ary or d-ary heap. It is a generalized form of the binary heap structure where each node has up to K children, unlike the binary heap structure with only 2 children. Because of this feature, the k-ary heap is a flexible and efficient data structure for priority queue implementations, this is more useful when the value of K is chosen optimally based on the specific application needs.
What is a K-ary Heap?A k-ary heap is a complete tree where each node has up to k children. Just like binary heaps (which are a special case with k=2), k-ary heaps can be min-heaps or max-heaps:
- Min-heap: The value of each node is less than or equal to the values of its children.
- Max-heap: The value of each node is greater than or equal to the values of its children.
Properties of K-ary Heaps- Complete Tree: A k-ary heap is always a complete tree, meaning all levels are fully filled except possibly the last level, which is filled from left to right.
- Height: The height of a K-ary heap with
n nodes are O(log_k(n)), which makes insertion and deletion operations efficient. - Parent and Child Relationship:
- For a node at the index
i (0-based index) in an array representation of the heap:- The index of the parent node is
(i - 1) // k. - The indices of the child nodes are
k * i + 1, k * i + 2, ..., k * i + k
Why Use a K-ary Heap?- Efficiency: For some operations, such as decrease-key, K-ary heaps can be more efficient than binary heaps. For example, a d-ary heap can decrease the height of the heap, reducing the time complexity of some operations.
- Flexibility: By adjusting the value of K, you can fine-tune the performance of the heap to suit specific needs, balancing between the cost of sift-up and sift-down operations.
Operations on K-ary Heaps- Insert: Adding a new element to the heap, maintaining the heap property.
- Extract-Min/Max: Remove and return the minimum or maximum element from the heap, then reheapify.
- Decrease-Key/Increase-Key: Decrease or increase the value of a key, and reheapify to maintain the heap property.
- Build-Heap: It provide us the feature of building a heap from an unsorted array of elements.
Implementing a K-ary Heap in PythonLet’s walk through the implementation of a k-ary heap in Python. We will create a class that supports basic heap operations such as insertion, extraction, and heapify.
Class Definition and Initialization
Python
class KaryHeap:
def __init__(self, k):
self.k = k
self.heap = []
def parent(self, i):
return (i - 1) // self.k
def child(self, i, j):
return self.k * i + j + 1
Insertion OperationThe insertion operation involves adding a new element to the end of the heap and then bubbling it up to maintain the heap property.
Python
def insert(self, value):
self.heap.append(value)
self._bubble_up(len(self.heap) - 1)
def _bubble_up(self, index):
parent_index = self.parent(index)
while index > 0 and self.heap[index] < self.heap[parent_index]:
self.heap[index], self.heap[parent_index] = self.heap[parent_index], self.heap[index]
index = parent_index
parent_index = self.parent(index)
Extraction OperationThe extraction operation (for a min-heap, extracting the minimum) involves removing the root element, replacing it with the last element, and then bubbling it down to maintain the heap property.
Python
def extract_min(self):
if len(self.heap) == 0:
return None
if len(self.heap) == 1:
return self.heap.pop()
root = self.heap[0]
self.heap[0] = self.heap.pop()
self._bubble_down(0)
return root
def _bubble_down(self, index):
smallest = index
for i in range(1, self.k + 1):
child_index = self.child(index, i - 1)
if child_index < len(self.heap) and self.heap[child_index] < self.heap[smallest]:
smallest = child_index
if smallest != index:
self.heap[index], self.heap[smallest] = self.heap[smallest], self.heap[index]
self._bubble_down(smallest)
Heapify OperationHeapify is used to build a heap from an arbitrary list of elements.
Python
def heapify(self, arr):
self.heap = arr
for i in reversed(range(len(self.heap) // self.k)):
self._bubble_down(i)
Examples to understand the K-ary Heap in PythonExample 1: Basic Operations on a K-ary HeapThis example demonstrates creating a 3-ary heap, inserting elements, and extracting the minimum element. This example demonstrates creating a 3-ary heap, inserting several elements into it, and then extracting the minimum element. The final state of the heap is printed after each operation to illustrate how the heap changes.
First we need to create a K-ar heap class then we need to perform our operations.
Python
class KaryHeap:
def __init__(self, k=2):
self.k = k
self.heap = []
def parent(self, i):
return (i - 1) // self.k
def children(self, i):
return [self.k * i + j + 1 for j in range(self.k) if self.k * i + j + 1 < len(self.heap)]
def insert(self, value):
self.heap.append(value)
self.sift_up(len(self.heap) - 1)
def sift_up(self, i):
while i > 0 and self.heap[i] < self.heap[self.parent(i)]:
self.heap[i], self.heap[self.parent(i)] = self.heap[self.parent(i)], self.heap[i]
i = self.parent(i)
def extract_min(self):
if len(self.heap) == 0:
return None
min_value = self.heap[0]
self.heap[0] = self.heap.pop()
self.sift_down(0)
return min_value
def sift_down(self, i):
while True:
smallest = i
for child in self.children(i):
if self.heap[child] < self.heap[smallest]:
smallest = child
if smallest != i:
self.heap[i], self.heap[smallest] = self.heap[smallest], self.heap[i]
i = smallest
else:
break
def build_heap(self, array):
self.heap = array[:]
for i in range(len(self.heap) // self.k, -1, -1):
self.sift_down(i)
def decrease_key(self, i, new_value):
if new_value > self.heap[i]:
raise ValueError("New value is greater than the current value")
self.heap[i] = new_value
self.sift_up(i)
# Create a ternary heap (3-ary heap)
heap = KaryHeap(k=3)
# Insert elements
heap.insert(10)
heap.insert(4)
heap.insert(7)
heap.insert(3)
heap.insert(5)
print("Heap after inserts:", heap.heap)
# Extract the minimum element
min_element = heap.extract_min()
print("Extracted min:", min_element)
print("Heap after extraction:", heap.heap)
OutputHeap after inserts: [3, 5, 7, 4, 10]
Extracted min: 3
Heap after extraction: [4, 5, 7, 10]
Example 2: Decreasing a KeyThis example shows how to decrease the value of an element in the heap. After inserting several elements, the key at a specific index is decreased, and the resulting heap structure is printed.
Python
class KaryHeap:
def __init__(self, k=2):
self.k = k
self.heap = []
def parent(self, i):
return (i - 1) // self.k
def children(self, i):
return [self.k * i + j + 1 for j in range(self.k) if self.k * i + j + 1 < len(self.heap)]
def insert(self, value):
self.heap.append(value)
self.sift_up(len(self.heap) - 1)
def sift_up(self, i):
while i > 0 and self.heap[i] < self.heap[self.parent(i)]:
self.heap[i], self.heap[self.parent(i)] = self.heap[self.parent(i)], self.heap[i]
i = self.parent(i)
def extract_min(self):
if len(self.heap) == 0:
return None
min_value = self.heap[0]
self.heap[0] = self.heap.pop()
self.sift_down(0)
return min_value
def sift_down(self, i):
while True:
smallest = i
for child in self.children(i):
if self.heap[child] < self.heap[smallest]:
smallest = child
if smallest != i:
self.heap[i], self.heap[smallest] = self.heap[smallest], self.heap[i]
i = smallest
else:
break
def build_heap(self, array):
self.heap = array[:]
for i in range(len(self.heap) // self.k, -1, -1):
self.sift_down(i)
def decrease_key(self, i, new_value):
if new_value > self.heap[i]:
raise ValueError("New value is greater than the current value")
self.heap[i] = new_value
self.sift_up(i)
# Create a ternary heap (3-ary heap)
heap = KaryHeap(k=3)
# Insert elements
heap.insert(10)
heap.insert(4)
heap.insert(7)
heap.insert(3)
heap.insert(5)
print("Heap before decreasing key:", heap.heap)
# Decrease the key at index 2 (value 7 to 2)
heap.decrease_key(2, 2)
print("Heap after decreasing key:", heap.heap)
OutputHeap before decreasing key: [3, 5, 7, 4, 10]
Heap after decreasing key: [2, 5, 3, 4, 10]
Example 3: Building a Heap from an ArrayThis example illustrates building a 3-ary heap directly from an unsorted array. The initial array is transformed into a heap, and the resulting structure is printed.
Python
class KaryHeap:
def __init__(self, k=2):
self.k = k
self.heap = []
def parent(self, i):
return (i - 1) // self.k
def children(self, i):
return [self.k * i + j + 1 for j in range(self.k) if self.k * i + j + 1 < len(self.heap)]
def insert(self, value):
self.heap.append(value)
self.sift_up(len(self.heap) - 1)
def sift_up(self, i):
while i > 0 and self.heap[i] < self.heap[self.parent(i)]:
self.heap[i], self.heap[self.parent(i)] = self.heap[self.parent(i)], self.heap[i]
i = self.parent(i)
def extract_min(self):
if len(self.heap) == 0:
return None
min_value = self.heap[0]
self.heap[0] = self.heap.pop()
self.sift_down(0)
return min_value
def sift_down(self, i):
while True:
smallest = i
for child in self.children(i):
if self.heap[child] < self.heap[smallest]:
smallest = child
if smallest != i:
self.heap[i], self.heap[smallest] = self.heap[smallest], self.heap[i]
i = smallest
else:
break
def build_heap(self, array):
self.heap = array[:]
for i in range(len(self.heap) // self.k, -1, -1):
self.sift_down(i)
def decrease_key(self, i, new_value):
if new_value > self.heap[i]:
raise ValueError("New value is greater than the current value")
self.heap[i] = new_value
self.sift_up(i)
# Create a ternary heap (3-ary heap)
heap = KaryHeap(k=3)
# Build the heap from an array
array = [9, 5, 6, 2, 3, 8]
heap.build_heap(array)
print("Heap after building from array:", heap.heap)
OutputHeap after building from array: [2, 3, 6, 9, 5, 8]
Example 4: Extracting All ElementsThis example demonstrates extracting all elements from the heap one by one. Each extracted element is stored in a list, and the list is printed to show the elements in sorted order.
Python
class KaryHeap:
def __init__(self, k=2):
self.k = k
self.heap = []
def parent(self, i):
return (i - 1) // self.k
def children(self, i):
return [self.k * i + j + 1 for j in range(self.k) if self.k * i + j + 1 < len(self.heap)]
def insert(self, value):
self.heap.append(value)
self.sift_up(len(self.heap) - 1)
def sift_up(self, i):
while i > 0 and self.heap[i] < self.heap[self.parent(i)]:
self.heap[i], self.heap[self.parent(i)] = self.heap[self.parent(i)], self.heap[i]
i = self.parent(i)
def extract_min(self):
if len(self.heap) == 0:
return None
min_value = self.heap[0]
self.heap[0] = self.heap.pop()
self.sift_down(0)
return min_value
def sift_down(self, i):
while True:
smallest = i
for child in self.children(i):
if self.heap[child] < self.heap[smallest]:
smallest = child
if smallest != i:
self.heap[i], self.heap[smallest] = self.heap[smallest], self.heap[i]
i = smallest
else:
break
def build_heap(self, array):
self.heap = array[:]
for i in range(len(self.heap) // self.k, -1, -1):
self.sift_down(i)
def decrease_key(self, i, new_value):
if new_value > self.heap[i]:
raise ValueError("New value is greater than the current value")
self.heap[i] = new_value
self.sift_up(i)
# Create a ternary heap (3-ary heap)
heap = KaryHeap(k=3)
# Insert elements
heap.insert(10)
heap.insert(4)
heap.insert(7)
heap.insert(3)
heap.insert(5)
print("Heap before extracting all elements:", heap.heap)
# Extract all elements
extracted_elements = []
while heap.heap:
extracted_elements.append(heap.extract_min())
print("Extracted elements in sorted order:", extracted_elements)
print("Heap after extracting all elements:", heap.heap)
Output:
Heap before extracting all elements: [3, 5, 7, 4, 10]
Extracted elements in sorted order: [3, 4, 5, 7, 10]
Heap after extracting all elements: [] Example 5: Using Different Values of KThis example shows how changing the value of K affects the heap structure. Heaps are built from the same array using different values of K (binary, ternary, and quaternary), and the resulting heaps are printed for comparison.
Python
class KaryHeap:
def __init__(self, k=2):
self.k = k
self.heap = []
def parent(self, i):
return (i - 1) // self.k
def children(self, i):
return [self.k * i + j + 1 for j in range(self.k) if self.k * i + j + 1 < len(self.heap)]
def insert(self, value):
self.heap.append(value)
self.sift_up(len(self.heap) - 1)
def sift_up(self, i):
while i > 0 and self.heap[i] < self.heap[self.parent(i)]:
self.heap[i], self.heap[self.parent(i)] = self.heap[self.parent(i)], self.heap[i]
i = self.parent(i)
def extract_min(self):
if len(self.heap) == 0:
return None
min_value = self.heap[0]
self.heap[0] = self.heap.pop()
self.sift_down(0)
return min_value
def sift_down(self, i):
while True:
smallest = i
for child in self.children(i):
if self.heap[child] < self.heap[smallest]:
smallest = child
if smallest != i:
self.heap[i], self.heap[smallest] = self.heap[smallest], self.heap[i]
i = smallest
else:
break
def build_heap(self, array):
self.heap = array[:]
for i in range(len(self.heap) // self.k, -1, -1):
self.sift_down(i)
def decrease_key(self, i, new_value):
if new_value > self.heap[i]:
raise ValueError("New value is greater than the current value")
self.heap[i] = new_value
self.sift_up(i)
# Create a binary heap (2-ary heap)
binary_heap = KaryHeap(k=2)
binary_heap.build_heap([9, 5, 6, 2, 3, 8])
print("Binary heap:", binary_heap.heap)
# Create a ternary heap (3-ary heap)
ternary_heap = KaryHeap(k=3)
ternary_heap.build_heap([9, 5, 6, 2, 3, 8])
print("Ternary heap:", ternary_heap.heap)
# Create a quaternary heap (4-ary heap)
quaternary_heap = KaryHeap(k=4)
quaternary_heap.build_heap([9, 5, 6, 2, 3, 8])
print("Quaternary heap:", quaternary_heap.heap)
OutputBinary heap: [2, 3, 6, 5, 9, 8]
Ternary heap: [2, 3, 6, 9, 5, 8]
Quaternary heap: [2, 5, 6, 9, 3, 8]
ConclusionK-ary heaps are versatile data structures that extend the binary heap by allowing each node to have up to K children, offering flexibility and efficiency in various applications. By optimizing the value of K, you can fine-tune the performance for specific needs, particularly for priority queue operations. Through examples of basic operations, key modification, heap construction, and different K values, we have illustrated the practical implementation and advantages of K-ary heaps in Python. This flexibility makes K-ary heaps a powerful tool in the arsenal of data structures, suitable for diverse computational tasks.
|
