힙은 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)
맥스힙 구현
class MaxHeap:
def __init__(self):
self.items = [None]
def insert(self, value):
self.items.append(value)
cur_index = len(self.items) - 1
while cur_index > 1: # cur_index 가 1이 되면 정상을 찍은거라 다른 것과 비교 안하셔도 됩니다!
parent_index = cur_index // 2
if self.items[parent_index] < self.items[cur_index]:
self.items[parent_index], self.items[cur_index] = self.items[cur_index], self.items[parent_index]
cur_index = parent_index
else:
break
def delete(self):
self.items[1], self.items[-1] = self.items[-1], self.items[1]
prev_max = self.items.pop()
cur_index = 1
while cur_index < len(self.items):
left_child_index = cur_index * 2
right_child_index = cur_index * 2 + 1
max_index = cur_index
print(max_index)
if left_child_index < len(self.items) and self.items[left_child_index] > self.items[max_index]:
max_index = left_child_index
if right_child_index < len(self.items) and self.items[right_child_index] > self.items[max_index]:
max_index = right_child_index
if max_index == cur_index:
break
self.items[cur_index], self.items[max_index] = self.items[max_index], self.items[cur_index]
return prev_max
연결되어 있는 정점와 정점간의 관계를 표현할 수 있는 자료구조
def dfs_stack(adjacent_graph, start_node):
visited = []
stack = [start_node]
while stack:
current_node = stack.pop()
visited.append(current_node)
for adjacent_node in adjacent_graph[current_node]:
if adjacent_node not in visited:
stack.append(adjacent_node)
return visited
def bfs_queue(adjacent_graph, start_node):
visited = []
queue = [start_node]
while queue:
current_node = queue.pop(0)
visited.append(current_node)
for adjacent_node in adjacent_graph[current_node]:
if adjacent_node not in visited:
queue.append(adjacent_node)
return visited