This is a Python program to implement a ternary heap.
The program creates a ternary max-heap and presents a menu to the user to perform various operations on it.
1. Create a class TernaryHeap with an instance variable items set to an empty list. This empty list is used to store the ternary heap.
2. Define methods size, parent, left, mid, right, get, get_max, extract_max, max_heapify, swap and insert.
3. The method size returns the number of elements in the heap.
4. The method parent takes an index as argument and returns the index of the parent.
5. The method left takes an index as argument and returns the index of its left child.
6. The method mid takes an index as argument and returns the index of its middle child.
7. The method right takes an index as argument and returns the index of its right child.
8. The method get takes an index as argument and returns the key at the index.
9. The method get_max returns the maximum element in the heap by returning the first element in the list items.
10. The method extract_max returns the the maximum element in the heap and removes it.
11. The method max_heapify takes an index as argument and modifies the heap structure at and below the node at this index to make it satisfy the heap property.
12. The method swap takes two indexes as arguments and swaps the corresponding elements in the heap.
13. The method insert takes a key as argument and adds that key to the heap.
Here is the source code of a Python program to implement a ternary heap. The program output is shown below.
class TernaryHeap: def __init__(self): self.items = [] def size(self): return len(self.items) def parent(self, i): return (i - 1)//3 def left(self, i): return 3*i + 1 def mid(self, i): return 3*i + 2 def right(self, i): return 3*i + 3 def get(self, i): return self.items[i] def get_max(self): if self.size() == 0: return None return self.items[0] def extract_max(self): if self.size() == 0: return None largest = self.get_max() self.items[0] = self.items[-1] del self.items[-1] self.max_heapify(0) return largest def max_heapify(self, i): l = self.left(i) r = self.right(i) m = self.mid(i) if (l <= self.size() - 1 and self.get(l) > self.get(i)): largest = l else: largest = i if (m <= self.size() - 1 and self.get(m) > self.get(largest)): largest = m if (r <= self.size() - 1 and self.get(r) > self.get(largest)): largest = r if (largest != i): self.swap(largest, i) self.max_heapify(largest) def swap(self, i, j): self.items[i], self.items[j] = self.items[j], self.items[i] def insert(self, key): index = self.size() self.items.append(key) while (index != 0): p = self.parent(index) if self.get(p) < self.get(index): self.swap(p, index) index = p theap = TernaryHeap() print('Menu (this assumes no duplicate keys)') print('insert <data>') print('max get') print('max extract') print('quit') while True: do = input('What would you like to do? ').split() operation = do[0].strip().lower() if operation == 'insert': data = int(do[1]) theap.insert(data) elif operation == 'max': suboperation = do[1].strip().lower() if suboperation == 'get': print('Maximum value: {}'.format(theap.get_max())) elif suboperation == 'extract': print('Maximum value removed: {}'.format(theap.extract_max())) elif operation == 'quit': break
1. Create an instance of TernaryHeap.
2. The user is presented with a menu to perform various operations on the heap.
3. The corresponding methods are called to perform each operation.
Case 1: Menu (this assumes no duplicate keys) insert <data> max get max extract quit What would you like to do? insert 3 What would you like to do? insert 1 What would you like to do? insert 7 What would you like to do? max extract Maximum value removed: 7 What would you like to do? max extract Maximum value removed: 3 What would you like to do? max extract Maximum value removed: 1 What would you like to do? max extract Maximum value removed: None What would you like to do? quit Case 2: Menu (this assumes no duplicate keys) insert <data> max get max extract quit What would you like to do? insert 10 What would you like to do? insert 2 What would you like to do? max get Maximum value: 10 What would you like to do? insert 15 What would you like to do? max extract Maximum value removed: 15 What would you like to do? max extract Maximum value removed: 10 What would you like to do? quit
Sanfoundry Global Education & Learning Series – Python Programs.
To practice all Python programs, here is complete set of 150+ Python Problems and Solutions.
- Practice Programming MCQs
- Check Python Books
- Apply for Programming Internship
- Check Information Technology Books
- Apply for Python Internship
