A max-heap implementation in Python >>> binary_heap = BinaryHeap() >>> binary_heap.insert(6) >>> binary_heap.insert(10) >>> binary_heap.insert(15) >>> binary_heap.insert(12) >>> binary_heap.pop() 15 >>> binary_heap.pop() 12 >>> binary_heap.get_list [1
| 1 | class BinaryHeap: |
| 2 | """ |
| 3 | A max-heap implementation in Python |
| 4 | >>> binary_heap = BinaryHeap() |
| 5 | >>> binary_heap.insert(6) |
| 6 | >>> binary_heap.insert(10) |
| 7 | >>> binary_heap.insert(15) |
| 8 | >>> binary_heap.insert(12) |
| 9 | >>> binary_heap.pop() |
| 10 | 15 |
| 11 | >>> binary_heap.pop() |
| 12 | 12 |
| 13 | >>> binary_heap.get_list |
| 14 | [10, 6] |
| 15 | >>> len(binary_heap) |
| 16 | 2 |
| 17 | """ |
| 18 | |
| 19 | def __init__(self): |
| 20 | self.__heap = [0] |
| 21 | self.__size = 0 |
| 22 | |
| 23 | def __swap_up(self, i: int) -> None: |
| 24 | """Swap the element up""" |
| 25 | temporary = self.__heap[i] |
| 26 | while i // 2 > 0: |
| 27 | if self.__heap[i] > self.__heap[i // 2]: |
| 28 | self.__heap[i] = self.__heap[i // 2] |
| 29 | self.__heap[i // 2] = temporary |
| 30 | i //= 2 |
| 31 | |
| 32 | def insert(self, value: int) -> None: |
| 33 | """Insert new element""" |
| 34 | self.__heap.append(value) |
| 35 | self.__size += 1 |
| 36 | self.__swap_up(self.__size) |
| 37 | |
| 38 | def __swap_down(self, i: int) -> None: |
| 39 | """Swap the element down""" |
| 40 | while self.__size >= 2 * i: |
| 41 | if 2 * i + 1 > self.__size: # noqa: SIM114 |
| 42 | bigger_child = 2 * i |
| 43 | elif self.__heap[2 * i] > self.__heap[2 * i + 1]: |
| 44 | bigger_child = 2 * i |
| 45 | else: |
| 46 | bigger_child = 2 * i + 1 |
| 47 | temporary = self.__heap[i] |
| 48 | if self.__heap[i] < self.__heap[bigger_child]: |
| 49 | self.__heap[i] = self.__heap[bigger_child] |
| 50 | self.__heap[bigger_child] = temporary |
| 51 | i = bigger_child |
| 52 | |
| 53 | def pop(self) -> int: |
| 54 | """Pop the root element""" |
| 55 | max_value = self.__heap[1] |
| 56 | self.__heap[1] = self.__heap[self.__size] |
| 57 | self.__size -= 1 |
| 58 | self.__heap.pop() |
| 59 | self.__swap_down(1) |
| 60 | return max_value |