# 위의 그래프를 예시로 삼아서 인접 리스트 방식으로 표현했습니다!
graph = {
    1: [2, 5, 9],
    2: [1, 3],
    3: [2, 4],
    4: [3],
    5: [1, 6, 8],
    6: [5, 7],
    7: [6],
    8: [5],
    9: [1, 10],
    10: [9]
}

def dfs_stack(adjacent_graph, start_node):
    visited = []
    stack = []

    stack.append(start_node)
    while len(stack) > 0:
        print(stack, visited)
        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 

print(dfs_stack(graph, 1))  # 1 이 시작노드입니다!
# [1, 9, 10, 5, 8, 6, 7, 2, 3, 4] 이 출력되어야 합니다!

class MaxHeap:
    def __init__(self):
        self.items = [None]
  # None이 무조건 맨 앞에 들어가 있어야 함

    def insert(self, value):
        self.items.append(value)

        if len(self.items) == 2:
            return

        cur_i = len(self.items) - 1
        while cur_i > 1:
            par_i = cur_i // 2
            
            if self.items[cur_i] > self.items[par_i]:
                self.items[cur_i], self.items[par_i] = self.items[par_i], self.items[cur_i]

                cur_i = par_i
            else:
                return

    def delete(self):
        biggest = self.items[1]

        self.items[1], self.items[-1] = self.items[-1], self.items[1]
        cur_i = 1
        
        while cur_i <= len(self.items) - 1:
            left_i = cur_i * 2
            right_i = cur_i * 2 + 1

            bigger_i = self.items.index(max(self.items[right_i], self.items[left_i]))

            if self.items[bigger_i] > self.items[cur_i]:
                self.items[bigger_i], self.items[cur_i] = self.items[cur_i], self.items[bigger_i]
            else:
                return biggest
            
        return biggest

max_heap = MaxHeap()
max_heap.insert(8)
max_heap.insert(6)
max_heap.insert(7)
max_heap.insert(2)
max_heap.insert(5)
max_heap.insert(4)
print(max_heap.items)  # [None, 8, 6, 7, 2, 5, 4]
print(max_heap.delete())  # 8 을 반환해야 합니다!
print(max_heap.items)  # [None, 7, 6, 4, 2, 5]