A Max Heap Implementation >>> unsorted = [103, 9, 1, 7, 11, 15, 25, 201, 209, 107, 5] >>> h = Heap() >>> h.build_max_heap(unsorted) >>> h [209, 201, 25, 103, 107, 15, 1, 9, 7, 11, 5] >>> >>> h.extract_max() 209 >>> h [201, 107, 25, 103, 11, 15, 1, 9, 7, 5]
| 23 | |
| 24 | |
| 25 | class Heap[T: Comparable]: |
| 26 | """A Max Heap Implementation |
| 27 | |
| 28 | >>> unsorted = [103, 9, 1, 7, 11, 15, 25, 201, 209, 107, 5] |
| 29 | >>> h = Heap() |
| 30 | >>> h.build_max_heap(unsorted) |
| 31 | >>> h |
| 32 | [209, 201, 25, 103, 107, 15, 1, 9, 7, 11, 5] |
| 33 | >>> |
| 34 | >>> h.extract_max() |
| 35 | 209 |
| 36 | >>> h |
| 37 | [201, 107, 25, 103, 11, 15, 1, 9, 7, 5] |
| 38 | >>> |
| 39 | >>> h.insert(100) |
| 40 | >>> h |
| 41 | [201, 107, 25, 103, 100, 15, 1, 9, 7, 5, 11] |
| 42 | >>> |
| 43 | >>> h.heap_sort() |
| 44 | >>> h |
| 45 | [1, 5, 7, 9, 11, 15, 25, 100, 103, 107, 201] |
| 46 | """ |
| 47 | |
| 48 | def __init__(self) -> None: |
| 49 | self.h: list[T] = [] |
| 50 | self.heap_size: int = 0 |
| 51 | |
| 52 | def __repr__(self) -> str: |
| 53 | return str(self.h) |
| 54 | |
| 55 | def parent_index(self, child_idx: int) -> int | None: |
| 56 | """ |
| 57 | returns the parent index based on the given child index |
| 58 | |
| 59 | >>> h = Heap() |
| 60 | >>> h.build_max_heap([103, 9, 1, 7, 11, 15, 25, 201, 209, 107, 5]) |
| 61 | >>> h |
| 62 | [209, 201, 25, 103, 107, 15, 1, 9, 7, 11, 5] |
| 63 | |
| 64 | >>> h.parent_index(-1) # returns none if index is <=0 |
| 65 | |
| 66 | >>> h.parent_index(0) # returns none if index is <=0 |
| 67 | |
| 68 | >>> h.parent_index(1) |
| 69 | 0 |
| 70 | >>> h.parent_index(2) |
| 71 | 0 |
| 72 | >>> h.parent_index(3) |
| 73 | 1 |
| 74 | >>> h.parent_index(4) |
| 75 | 1 |
| 76 | >>> h.parent_index(5) |
| 77 | 2 |
| 78 | >>> h.parent_index(10.5) |
| 79 | 4.0 |
| 80 | >>> h.parent_index(209.0) |
| 81 | 104.0 |
| 82 | >>> h.parent_index("Test") |
no outgoing calls
no test coverage detected