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._heapify_up(len(self.heap) - 1)
# O(log n), O(1)
def _heapify_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._heapify_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 extract_min(self):
if not self.heap:
return None
min_value = self.heap0
if len(self.heap) > 1:
self.heap0 = self.heap.pop()
self._heapify_down()
else:
self.heap.pop()
return min_value
# O(log n), O(1)
def _heapify_down(self, index=0):
left_child = 2 * index + 1
if left_child >= len(self.heap):
return
if self.heapleft_child < self.heapindex:
self.heapindex, self.heapleft_child = self.heapleft_child, self.heapindex
self._heapify_down(left_child)
def test_insert_and_extract():
heap = Heap()
heap.insert(5)
heap.insert(3)
heap.insert(7)
heap.insert(1)
assert heap.extract_min() == 1
assert heap.extract_min() == 3
assert heap.extract_min() == 5
assert heap.extract_min() == 7
assert heap.extract_min() 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.extract_min() 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.extract_min() == 1
assert heap.extract_min() == 3
assert heap.extract_min() == 3
assert heap.extract_min() == 5