[자료구조] 우선순위 큐(Priority Queue), 힙(Heap),트리(Tree)

우선순위 큐(Priority Queue),  힙(Heap)

* 우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조이다.

 

 

* 힙은 완전 이진 트리 자료구조의 일종, 힙에서는 항상 루트 노드를 제거

① 최소 힙 (min heap) : 루트 노드가 가장 작은 값을 가짐, 값이 작은 데이터가 우선적으로 제거

② 최대 힙 (max heap): 루트 노드가 가장 큰 값을 가짐, 값이 큰 데이터가 우선적으로 제거

 

* 완전 이진 트리(Complete Binary Tree) :  루트 노드부터 시작하여 왼쪽 자식 노드, 오른쪽 자식 노드 순으로 데이터가 차례대로 삽입되는 트리를 의미

완전이진트리

 

* 최소 힙 구성 함수 : Min-Heapify()

: (상향식)부모노드로 거슬러 올라가며, 부모보다 자신의 값이 더 작은 경우에 위치를 교체.

=> 새로운 원소가 삽입되었을 때 O(logN)의 시간 복잡도로 힙 성질을 유지하도록 할 수 있음.

=> 원소가 제거 될 때 O(logN) 시간 복잡도로 힙 성질을 유지하도록 할 수 있음.

#파이썬은 기본적으로 최소힙 지원
#max heap을 원하면 넣을때랑 뺄때 - 붙여서 하면 됨
import sys
import heapq
input = sys.stdin.readline

def heapsort(iterable):
    h = []
    result = []
    #모든 원소를 차례대로 힙에 삽입
    for value in iterable:
        heapq.heappush(h, value)
    #힙에 삽입된 모든 원소를 차례대로 꺼내 담기
    for i in range(len(h)):
        result.append(heapq.heappop(h))
    return result
    
n = int(input())    
arr=[]

for i in range(n):
    arr.append(int(input()))
    
res = heapsort(arr)    

for i in range(n):
    print(res[i])

 

 

 

트리(Tree)

: 가계도와 같은 계층적인 구조를 표현할 때 사용할 수 있는 자료구조.

 

<관련 용어>

① 루트노드(root node) : 부모가 없는 최상위 노드

② 단말 노드(leaf node) : 자식이 없는 노드

③ 크기(size) : 트리에 포함된 모든 노드의 개수

④ 깊이(depth) : 루트 노드부터의 거리

⑤ 높이(height) : 깊이 중 최댓값

⑥ 차수(degree) : 각 노드의 자식방향 간선 개수

-> 기본적으로 트리의 크기가 N이면 전체 간선 개수는 N-1 개 이다.

 

 

* 이진 탐색 트리(Binary Search Tree)

이진 탐색이 동작할 수 있도록 고안된 효율적인 탐색이 가능한 자료구조의 일종.

이진 탐색 트리의 특징은 왼쪽 자식 노드 값 < 부모 노드 값 < 오른쪽 자신 노드 값 으로 표현된다는 점이다.

 

 

* 트리 순회 (Tree Traversal)

: 트리 자료구조에 포함된 노드를 특정한 방법으로 한 번씩 방문하는 방법 의미

① 전위 순회(pre-order traverse) : 루트를 먼저 방문하고 왼쪽 하위 자식, 오른쪽 하위 자식 노드 방문

② 중위 순회(in-order traverse) : 왼쪽 하위 자식을 방문한 뒤 루트, 오른쪽 하위 자식 노드 방문

③ 후위 순회(post-order traverse) : 하위 자식을 모두 방문 후 루트를 방문

 

class Node:
    def __init__(self, data, left_node, right_node):
        self.data = data
        self.left_node = left_node
        self.right_node = right_node
        
#전위순회
def pre_order(node):
    print(node.data, end=' ') #자신의 데이터를 먼저 처리 한 뒤에
    if node.left_node != None:
        pre_order(tree[node.left_node]) #이어서 왼쪽노드 방문처리
    if node.right_node != None:
        pre_order(tree[node.right_node]) #이어서 오른쪽노드 방문처리
        
#중위순회
def in_order(node):    
    if node.left_node != None:
        in_order(tree[node.left_node]) #왼쪽 먼저 방문
    print(node.data, end=' ') #자기 자신 처리
    if node.right_node != None:
        in_order(tree[node.right_node]) #오른쪽 방문
        
#후위순회
def post_order(node):    
    if node.left_node != None:
        post_order(tree[node.left_node]) #왼쪽 방문
    if node.right_node != None:
        post_order(tree[node.right_node]) #오른쪽 방문
    print(node.data, end=' ') #마지막으로 자기 자신 처리
    
n = int(input())    
tree = {}

for i in range(n):
    data, left_node, right_node = input().split()
    if left_node == "None":
        left_node = None
    if right_node == "None":
        right_node = None
    tree[data] = Node(data, left_node, right_node)
    
pre_order(tree['A'])
print()
in_order(tree['A'])
print()
post_order(tree['A'])
print()

 

 

 

 

 

 

 

이코테 2021 강의를 듣고 정리한 글이다.