航行99-3週間WIL
WIL
バイナリツリー
structure.py
structure.py
バイナリツリー
structure.py
class TreeNode:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
make_binary_tree.pyfrom binarytree.structures import TreeNode
def make_tree_by(lst, idx):
parent = None
if idx < len(lst):
value = lst[idx]
if value == None:
return
parent = TreeNode(value)
parent.left = make_tree_by(lst, 2 * idx + 1)
parent.left = make_tree_by(lst, 2 * idx + 2)
return parent
お尻structure.py
class BinaryMaxHeap:
def __init__(self):
# 계산 편의를 위해 0이 아닌 1번째 인덱스부터 사용한다.
self.items = [None]
def __len__(self):
# len() 연산을 가능하게 하는 매직 메서드 덮어쓰기(Override).
return len(self.items) - 1
def _percolate_up(self):
# percolate: 스며들다.
cur = len(self)
# left 라면 2*cur, right 라면 2*cur + 1 이므로 parent 는 항상 cur // 2
parent = cur // 2
while parent > 0:
if self.items[cur] > self.items[parent]:
self.items[cur], self.items[parent] = self.items[parent], self.items[cur]
cur = parent
parent = cur // 2
def _percolate_down(self, cur):
biggest = cur
left = 2 * cur
right = 2 * cur + 1
if left <= len(self) and self.items[left] > self.items[biggest]:
biggest = left
if right <= len(self) and self.items[right] > self.items[biggest]:
biggest = right
if biggest != cur:
self.items[cur], self.items[biggest] = self.items[biggest], self.items[cur]
self._percolate_down(biggest)
def insert(self, k):
self.items.append(k)
self._percolate_up()
def extract(self):
if len(self) < 1:
return None
root = self.items[1]
self.items[1] = self.items[-1]
self.items.pop()
self._percolate_down(1)
return root
maxheap.pydef test_maxheap_we_made(lst, k):
maxheap = BinaryMaxHeap()
# for 문을 눈여겨봐두세요.
# 힙정렬 시간복잡도 계산의 토대입니다.
for elem in lst:
maxheap.insert(elem)
return [maxheap.extract() for _ in range(k)][k - 1]
泡の位置合わせdef bubblesort(lst):
# 최댓값을 구하는 알고리즘을 len(lst) - 1 만큼 반복한다.
iters = len(lst) - 1
for iter in range(iters):
# 이미 구한 최댓값은 범위에서 제외한다.
wall = iters - iter
for cur in range(wall):
if lst[cur] > lst[cur + 1]:
lst[cur], lst[cur + 1] = lst[cur + 1], lst[cur]
return lst
ソートの選択def selectionsort(lst):
iters = len(lst) - 1
for iter in range(iters):
minimum = iter
for cur in range(iter + 1, len(lst)):
if lst[cur] < lst[minimum]:
minimum = cur
if minimum != iter:
lst[minimum], lst[iter] = lst[iter], lst[minimum]
return lst
整列挿入def insertionsort(lst):
# 0번째 요소는 이미 정렬되어있으니, 1번째 ~ lst(len)-1 번째를 정렬하면 된다.
for cur in range(1, len(lst)):
# 비교지점이 cur-1 ~ 0(=cur-cur)까지 내려간다.
for delta in range(1, cur + 1):
cmp = cur - delta
if lst[cmp] > lst[cmp + 1]:
lst[cmp], lst[cmp + 1] = lst[cmp + 1], lst[cmp]
else:
break
return lst
Reference
この問題について(航行99-3週間WIL), 我々は、より多くの情報をここで見つけました https://velog.io/@vivala0519/항해99-3주차-회고テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol