Heap
code: python
from typing import List, Any, Optional
class Heap:
def __init__(self):
self.heap: ListAny = []
# O(log n), O(1)
def insert(self, value: Any) -> None:
self.heap.append(value)
self._up(len(self.heap) - 1)
# O(log n), O(1)
def _up(self, index: int) -> None:
parent = (index - 1) // 2
if index > 0 and self.heapindex < self.heapparent:
self.heapindex, self.heapparent = self.heapparent, self.heapindex
self._up(parent)
# O(1), O(1)
def get(self) -> OptionalAny:
return self.heap0 if self.heap else None
# 0
# / \
# 1 2
# / \ / \
# 3 4 5 6
# # O(log n), O(1)
def pop(self):
if not self.heap:
return None
min_value = self.heap0
if len(self.heap) > 1:
self.heap0 = self.heap.pop()
self._down()
else:
self.heap.pop()
return min_value
# O(log n), O(1)
def _down(self, index=0):
smallest = index
left_child = 2 * index + 1
right_child = 2 * index + 2
if left_child < len(self.heap) and self.heapleft_child < self.heapsmallest:
smallest = left_child
if right_child < len(self.heap) and self.heapright_child < self.heapsmallest:
smallest = right_child
if smallest != index:
self.heapindex, self.heapsmallest = self.heapsmallest, self.heapindex
self._down(smallest)
def test_insert_and_extract():
heap = Heap()
heap.insert(5)
heap.insert(3)
heap.insert(7)
heap.insert(1)
assert heap.pop() == 1
assert heap.pop() == 3
assert heap.pop() == 5
assert heap.pop() == 7
assert heap.pop() is None
def test_get():
heap = Heap()
assert heap.get() is None
heap.insert(5)
heap.insert(3)
assert heap.get() == 3
heap.insert(1)
assert heap.get() == 1
def test_empty_heap():
heap = Heap()
assert heap.pop() is None
assert heap.get() is None
def test_insert_duplicate_values():
heap = Heap()
heap.insert(5)
heap.insert(3)
heap.insert(3)
heap.insert(1)
assert heap.pop() == 1
assert heap.pop() == 3
assert heap.pop() == 3
assert heap.pop() == 5