Heap Sort

code: python

from typing import List, Any

# O(nlogn), O(1)

def heap_sort(arr):

n = len(arr)

heap = Heap()

for v in arr:

heap.insert(v)

res = []

for _ in range(n):

res.append(heap.pop())

return res

class Heap:

def __init__(self):

self.heap: ListAny = []

def insert(self, value: Any) -> None:

self.heap.append(value)

self._up(len(self.heap) - 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)

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

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_heap_sort():