[내배캠/TIL(8/3)]알고리즘-힙, 그래프

손홍서·2022년 8월 3일
0

day72 TIL

힙은 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(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 

그래프

연결되어 있는 정점와 정점간의 관계를 표현할 수 있는 자료구조

dfs(stack)

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

bfs(queue)

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
profile
Hello World!!

0개의 댓글